题目大意
有一个 N×M(1≤N,M≤1,000) 的棋盘，Bessie 开始时在左上角的格子，她要移动到右下角的格子上。当 Bessie 位于一个格子上时，她只能移动到与之有公共边的相邻格子。棋盘上的格子按照颜色可分为红、粉、橙、绿、紫五类。
- 红色格子：不能通过。
- 粉色格子：可以自由通过。
- 橙色格子：可以自由通过，但 Bessie 通过橙色格子后会沾上橙子味。
- 绿色格子：当且仅当 Bessie 身上有橙子味时，Bessie才能通过绿色格子。
- 紫色格子：Bessie 会在上面漂移（除非她漂移的方向上有一个不能通过的格子），并且 Bessie 身上的橙子味会消失。举个例子，如果 Bessie 从紫色格子左边的格子移动到紫色格子上，
- 如果右边是粉/橙色格子：Bessie 会滑到右边。
- 如果右边是红/绿色格子，或者右边是边界：Bessie 会停在当前紫色格子上。
- 如果右边仍然是紫色格子：Bessie 会滑到右边，然后继续根据这一规定来漂移。
请问 Bessie 最少需要移动多少步。
题目分析
不难看出，这题是一道搜索题。
考虑使用 bfs , 每个状态有五个元素，
分别表示 当前状态所在的坐标 x,y ，当前状态上一步移动的方向（为“漂移”操作所设置） ，当前状态是否有气味 f ，到当前状态所经过的步数 step。
然后分情况讨论，若是紫色格子，我们就考虑“漂移”，其余正常按题目转移即可。
（漂移的细节详见代码）
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int MAXN=1e3+100; 4 5 struct Node{ 6 int x,y,dir,f,step; 7 }; 8 9 int dx[5]={1,-1,0,0}; 10 int dy[5]={0,0,1,-1}; 11 12 int n,m; 13 int a[MAXN][MAXN]; 14 bool vis[MAXN][MAXN][3][5]; 15 queue<Node> q; 16 inline int bfs(){ 17 q.push((Node){1,1,0,0,0}); 18 while(!q.empty()){ 19 Node fa=q.front();q.pop(); 20 if(vis[fa.x][fa.y][fa.f][fa.dir]) continue; 21 vis[fa.x][fa.y][fa.f][fa.dir]=1; 22 if(fa.x==n&&fa.y==m) return fa.step; 23 24 bool flag=false; 25 if(a[fa.x][fa.y]==4){ 26 int xx=fa.x+dx[fa.dir],yy=fa.y+dy[fa.dir]; 27 if(!a[xx][yy]||a[xx][yy]==3); 28 else if(a[xx][yy]==1||a[xx][yy]==4){ 29 q.push((Node){xx,yy,fa.dir,0,fa.step+1}); 30 flag=1; 31 } 32 else{ 33 q.push((Node){xx,yy,fa.dir,1,fa.step+1}); 34 flag=1; 35 } 36 } 37 if(a[fa.x][fa.y]==4&&flag) continue; 38 for(int i=0;i<4;++i){ 39 int xx=fa.x+dx[i],yy=fa.y+dy[i]; 40 if(!a[xx][yy]||(a[xx][yy]==3&&!fa.f)) continue; 41 else if((a[xx][yy]==3&&fa.f)||a[xx][yy]==1||a[xx][yy]==4){ 42 q.push((Node){xx,yy,i,fa.f,fa.step+1}); 43 } 44 else if(a[xx][yy]==2) 45 q.push((Node){xx,yy,i,1,fa.step+1}); 46 } 47 } 48 return -1; 49 } 50 int main(){ 51 // freopen("dream.in","r",stdin); 52 // freopen("dream.out","w",stdout); 53 scanf("%d%d",&n,&m); 54 for(int i=1;i<=n;++i) 55 for(int j=1;j<=m;++j) 56 scanf("%d",&a[i][j]); 57 printf("%d ",bfs()); 58 return 0; 59 }