直接bfs，在過程中更新方案數(shù)即可

#include<iostream> #include<cstdio> #include<queue> using namespace std; const int N=55,inf=1e9,dx[]={1,1,-1,-1,2,2,-2,-2},dy[]={2,-2,2,-2,1,-1,1,-1}; int n,m,a[N][N],b[N][N],dis[N][N]; long long f[N][N]; bool v[N][N]; struct qwe {int x,y;qwe(int X=0,int Y=0){x=X,y=Y;} }s,t; queue<qwe>q; int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){scanf("%d",&a[i][j]);b[i][j]=dis[i][j]=inf;if(a[i][j]==3)s=qwe(i,j);if(a[i][j]==4)t=qwe(i,j);}q.push(s);v[s.x][s.y]=1;b[s.x][s.y]=dis[s.x][s.y]=0;f[s.x][s.y]=1;while(!q.empty()){qwe u=q.front();q.pop();v[u.x][u.y]=0;for(int k=0;k<8;k++){int x=u.x+dx[k],y=u.y+dy[k];if(x<1||y<1||x>n||y>m||a[x][y]==2)continue;int nw=b[u.x][u.y]+(a[x][y]==0);if(nw<b[x][y]){b[x][y]=nw;dis[x][y]=dis[u.x][u.y]+1;f[x][y]=f[u.x][u.y];if(!v[x][y]){v[x][y]=1;q.push(qwe(x,y));}}else if(nw==b[x][y]){if(dis[u.x][u.y]+1<dis[x][y]){dis[x][y]=dis[u.x][u.y]+1;f[x][y]=f[u.x][u.y];if(!v[x][y]){v[x][y]=1;q.push(qwe(x,y));}}else if(dis[u.x][u.y]+1==dis[x][y]){f[x][y]+=f[u.x][u.y];if(!v[x][y]){v[x][y]=1;q.push(qwe(x,y));}}}}}if(b[t.x][t.y]==inf)puts("-1");else printf("%d\n%d\n%lld\n",b[t.x][t.y],dis[t.x][t.y],f[t.x][t.y]);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/lokiii/p/9570655.html

總結(jié)

以上是生活随笔為你收集整理的bzoj 1632: [Usaco2007 Feb]Lilypad Pond【bfs】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。