1 条题解
-
0Guest LV 0 MOD
-
0
#include<iostream> using namespace std; const int N=101; int n,m,r,a[N][N]; bool flag=false; int dx[5]={0,1,-1,0,0},dy[5]={0,0,0,1,-1}; bool shit[N][N][N]; struct node { int x,y,num,time; }h[10000001]; void sb() { int head=0,tail=1; h[1].x=1,h[1].y=1,h[1].num=0,h[1].time=0; shit[1][1][0]=1; while(head<tail) { head++; for(int i=1;i<=4;i++) { int xx,yy; for(int j=1;j<=n;j++) { xx=h[head].x+dx[i]*j,yy=h[head].y+dy[i]*j; if(xx<1||xx>n||yy<1||yy>m) { break; } if(a[xx][yy]==1) { continue; } tail++; h[tail].x=xx,h[tail].y=yy; h[tail].num=h[head].num,h[tail].time=h[head].time+1; if(j>1) { h[tail].num+=j; } if(h[tail].num>r) { tail--; break; } if(shit[xx][yy][h[tail].num]==1) { tail--; continue; } shit[xx][yy][h[tail].num]=1; if(xx==n&&yy==m) { cout<<h[tail].time; flag=true; return ; } } } } } int main() { cin>>n>>m>>r; char c; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>c; if(c=='P') { a[i][j]=0; } else { a[i][j]=1; } } } sb(); if(!flag) { cout<<"Impossible"; } return 0; }
- 1