学步园

//BFS宽度优先搜索<br /> //G[x][y][k]表示走到(x,y)后还能飞k步的最优值<br /> #include<cstdio><br /> #include<iostream><br /> #include<cstring><br /> #include<queue><br /> using namespace std;<br /> const int MAX = 102;<br /> const int dir[4][2] = {1,0,-1,0,0,1,0,-1};<br /> int N,M,D,ans;<br /> int G[MAX][MAX][MAX];<br /> bool P[MAX][MAX],vis[MAX][MAX][MAX];<br /> struct node<br /> {<br /> int x,y,d;<br /> }Q[MAX*MAX*MAX];<br /> int hd,tl;<br /> void Push(int x,int y,int d)<br /> {<br /> Q[tl].x = x;<br /> Q[tl].y = y;<br /> Q[tl++].d = d;<br /> }<br /> void init()//初始化，一开始所有状态都不可达，记为MAX*MAX<br /> {<br /> hd = tl = 0;<br /> for(int i = 1;i <= N;++i)<br /> for(int j = 1;j <= M;++j)<br /> for(int k = 0;k <= D;++k)<br /> G[i][j][k] = MAX*MAX;<br /> G[1][1][D] = 0;<br /> }<br /> bool legal(int x,int y)<br /> {<br /> if(x < 1 || x > N || y < 1 || y > M || !P[x][y]) return false;<br /> return true;<br /> }<br /> void BFS()<br /> {<br /> int tx,ty,td,X,Y;<br /> init();<br /> Push(1,1,D);//初始点进队<br /> vis[1][1][D] = 1;<br /> while(hd < tl)<br /> {<br /> tx = Q[hd].x;<br /> ty = Q[hd].y;<br /> td = Q[hd++].d;<br /> for(int i = 0;i < 4;++i)//枚举4个方向<br /> {<br /> for(int j = 1;j <= td;++j)//处理飞的情况<br /> {<br /> X = tx + j*dir[i][0];<br /> Y = ty + j*dir[i][1];<br /> if(!legal(X,Y) || vis[X][Y][td-j]) continue;<br /> G[X][Y][td-j] = min(G[X][Y][td-j],G[tx][ty][td]+1);<br /> Push(X,Y,td-j);<br /> vis[X][Y][td-j] = 1;<br /> if(X == N && Y == M) return;<br /> }<br /> X = tx + dir[i][0];//走路的<br /> Y = ty + dir[i][1];<br /> if(!legal(X,Y) || vis[X][Y][td]) continue;<br /> G[X][Y][td] = min(G[X][Y][td],G[tx][ty][td]+1);<br /> Push(X,Y,td);<br /> vis[X][Y][td] = 1;<br /> if(X == N && Y == M) return;<br /> }<br /> }<br /> }<br /> int main()<br /> {<br /> //freopen("in.txt","r",stdin);<br /> char str[MAX];<br /> scanf("%d%d%d",&N,&M,&D);<br /> for(int i = 1;i <= N;++i)<br /> {<br /> scanf("%s",str);<br /> for(int j = 0;j < M;++j)<br /> if(str[j] == 'P')<br /> P[i][j+1] = 1;<br /> }<br /> BFS();<br /> ans = G[N][M][D];<br /> for(int i = 0;i < D;++i)<br /> ans = min(ans,G[N][M][i]);<br /> if(ans != MAX*MAX)<br /> printf("%d/n",ans);<br /> else printf("impossible/n");<br /> }