刚开是我用了一种很笨的bfs过掉的,后来看到原来还可以三维带状态BFS,觉得是一个不错的思路。
d[x][y][k]表示坐标位于(x,y)经过K个障碍到达时的最短路径,当然如果(x,y)处的数字是0就不用处理多个障碍的情况,因为第一次到达它一定是最短路径。
AC代码:
#include<cstdio> #include<cstring> #include<queue> #include<cstdlib> using namespace std; const int maxn=22; int d[maxn][maxn][maxn],G[maxn][maxn]; int n,m,k; const int dx[]={1,-1,0,0}; const int dy[]={0,0,1,-1}; struct node{ int x,y; //坐标 int dis; //经过了多少障碍 node(){ } node(int x,int y,int dis):x(x),y(y),dis(dis){ } }; int bfs(){ memset(d,-1,sizeof(d)); queue<node>q; d[0][0][0]=0; q.push(node(0,0,0)); while(!q.empty()){ node p=q.front(); q.pop(); int x=p.x,y=p.y,dis=p.dis; if(x==n-1&&y==m-1) return d[x][y][0]; for(int i=0;i<4;++i){ int px=x+dx[i],py=y+dy[i]; if(px<0||py<0||px>=n||py>=m) continue; if(G[px][py]==1){ if(dis>=k||d[px][py][dis+1]!=-1) continue; d[px][py][dis+1]=d[x][y][dis]+1; q.push(node(px,py,dis+1)); } else { if(d[px][py][0]!=-1) continue; d[px][py][0]=d[x][y][dis]+1; q.push(node(px,py,0)); } } } return -1; } int main(){ int T; scanf("%d",&T); while(T--){ scanf("%d%d%d",&n,&m,&k); for(int i=0;i<n;++i) for(int j=0;j<m;++j){ scanf("%d",&G[i][j]); } int ans=bfs(); printf("%d\n",ans); } return 0; }
如有不当之处欢迎指出!