bfs搜索
每个时间段胖子的体型不同 ， 分为三种 ，所以我们要分三种判别的方式
因为样例保证能找到出路，所以在胖子很胖的时候被可能被恰住，但是变成1的时候一定不会被卡住，所以我们直接把体积t!=1的时候胖子的位置再加入队列中，但是时间加1 ，这样的话就可以实现胖子原地呆1步；
#include<iostream> #include<cstring> #include<algorithm> #include<queue> using namespace std ; const int N = 310 ; char mp[N][N] ; int d[4][2] = {{0,1},{0,-1},{1,0},{-1,0}} ; int n , k ,t; bool v[N][N] ; struct node{ int x, y ,dis ; node(int xx, int yy , int diss){ x = xx , y = yy , dis = diss ; } }; queue<node> q; bool check_5(int x,int y){ if(v[x][y]) return false ; for(int i = x-2; i <= x +2 ; i ++){ for(int j = y-2; j <= y +2 ; j ++){ if(i < 0 || i >= n|| j < 0|| j >= n ) return false ; if(mp[i][j] == '*') return false ; } } return true ; } bool check_3(int x,int y){ if(v[x][y]) return false ; for(int i = x-1; i <= x +1 ; i ++){ for(int j = y-1; j <= y +1 ; j ++){ if(i < 0 || i >= n|| j < 0|| j >= n ) return false ; if( mp[i][j] == '*') return false ; } } return true ; } bool check_1(int x,int y){ if(v[x][y]) return false ; if(x < 0 || x >= n|| y < 0|| y >= n ) return false ; if( mp[x][y] == '*') return false ; return true ; } void bfs(){ q.push(node(2,2,0)) ; while(!q.empty()){ node now = q.front() ; q.pop() ; int x = now.x , y = now.y ; if(x == n-3 && y == n-3) { cout << now.dis << endl ; return ; } if(now.dis < k) t = 5 ; else if(now.dis >= k&& now.dis < 2*k) t = 3 ; else if(now.dis >= 2*k) t = 1; if(t!=1) q.push(node(x,y,now.dis+1)) ; for(int i = 0 ; i < 4 ; i ++){ int tx = x +d[i][0], ty = y + d[i][1] ; if(t==5){ if(check_5(tx,ty) ) { v[tx][ty] = 1 ; q.push(node(tx,ty,now.dis+1)) ; } } else if(t==3) { if(check_3(tx,ty)){ v[tx][ty] = 1 ; q.push(node(tx,ty,now.dis+1)) ; } } else if(t == 1){ if(check_1(tx,ty)){ v[tx][ty] = 1 ; q.push(node(tx,ty,now.dis+1)) ; } } } } } int main(){ cin >> n >> k ; for(int i = 0; i < n ; i ++) cin >> mp[i] ; v[2][2] = 1 ; bfs(); return 0 ; }
