做题感悟:这种题只要将方向作为第三维标记即可,但是这题因为漏想了一个地方导致改了老半天。
解题思路:只要将方向作为第三维标记,还要注意如果左右能走就不走前,只有左右都为石头时才走前,且不能反方向走(可以走走过的路)。
代码:
#include<stdio.h> #include<iostream> #include<map> #include<stack> #include<string> #include<string.h> #include<stdlib.h> #include<math.h> #include<vector> #include<queue> #include<algorithm> using namespace std ; #define LEN sizeof(struct node) #define pret(a,b) memset(a,b,sizeof(a)) #define lld __int64 const double PI = 3.1415926 ; const double INF = 999999999 ; const double esp = 1e-4 ; const lld md= 2810778 ; const int MX = 81 ; int n,m ; char s[MX][MX] ; bool vis[MX][MX][4] ; int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1} ; // 下 0 上 1 右 2 左 3 int dr[4][4]={{1,0,2},{0,1,3},{2,3,0},{3,2,1}} ;// 东 西 南 北 0 1 2 3 int dc[4][4]={{3,2,0},{2,3,1},{0,1,2},{1,0,3}} ; // 走完后对应的方向 struct node { int x,y,step,cnt ; } ; bool search(int x,int y) { if(x<0||x>=n||y<0||y>=m||s[x][y]=='#') return false ; return true ; } int bfs(int x,int y) { int sx,sy,cnt ; queue<node>q ; node curt,next ; memset(vis,false,sizeof(vis)) ; curt.x=x ; curt.y=y ; curt.step=0 ; for(int i=0 ;i<4 ;i++) // 初始化四个方向 { curt.cnt=i ; vis[x][y][i]=true ; q.push(curt) ; } while(!q.empty()) { curt=q.front() ; q.pop() ; x=curt.x ; y=curt.y ; cnt=curt.cnt ; // cnt 方向 if(!x||!y||x==n-1||y==m-1) return curt.step ; bool fx=false ; for(int i=0 ;i<3 ;i++) { int z=dr[cnt][i] ; next.x=sx=x+dx[z] ; next.y=sy=y+dy[z] ; next.step=curt.step+1 ; if(search(sx,sy)&&(!fx||i<2)) { int mx=dc[cnt][i] ; // 方向 if(!vis[sx][sy][mx]) { next.cnt=mx ; vis[sx][sy][mx]=true ; q.push(next) ; fx=true ; } else fx=true ; // fx 标记左右是否可走,开始忘记了这个!!! } } } return -1 ; } int main() { int Tx,sx,sy ; scanf("%d",&Tx) ; while(Tx--) { scanf("%d%d",&n,&m) ; for(int i=0 ;i<n ;i++) { scanf("%s",s[i]) ; for(int j=0 ;j<m ;j++) { if(s[i][j]=='@') //记录起始位置 { sx=i ; sy=j ; } } } printf("%d\n",bfs(sx,sy)) ; } return 0 ; }