<quote> After eating too much fruit in Farmer John's kitchen, Bessie the cow is getting some very strange dreams! In her most recent dream, she is trapped in a maze in the shape of an N×MN×M grid of tiles (1≤N,M≤1,0001≤N,M≤1,000). She starts on the top-left tile and wants to get to the bottom-right tile. When she is standing on a tile, she can potentially move to the adjacent tiles in any of the four cardinal directions.
But wait! Each tile has a color, and each color has a different property! Bessie's head hurts just thinking about it:

If a tile is red, then it is impassable.
If a tile is pink, then it can be walked on normally.
If a tile is orange, then it can be walked on normally, but will make Bessie smell like oranges.
If a tile is blue, then it contains piranhas that will only let Bessie pass if she smells like oranges.
If a tile is purple, then Bessie will slide to the next tile in that direction (unless she is unable to cross it). If this tile is also a purple tile, then Bessie will continue to slide until she lands on a non-purple tile or hits an impassable tile. Sliding through a tile counts as a move. Purple tiles will also remove Bessie's smell.
(If you're confused about purple tiles, the example will illustrate their use.)

</quote>

``````#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int N=1005;
int n,m,a[N][N];
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
struct Node
{
int x,y,d;
bool orange;
};
queue<Node> q;
int step[N][N][5][3];
bool check(Node f)
{
int x=dx[f.d]+f.x,y=dy[f.d]+f.y;
return a[x][y]!=0&&a[x][y]!=3;
}
int main()
{
freopen("dream.in","r",stdin);
freopen("dream.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
memset(step,-1,sizeof(step));
step[1][1][0][0]=step[1][1][2][0]=0; //初始步数为0
q.push((Node){1,1,0,false}); //方向为向下或向右
q.push((Node){1,1,2,false});
while(!q.empty())
{
Node f=q.front();
q.pop();
for(int i=0;i<4;i++)
{
int x=f.x+dx[i],y=f.y+dy[i];
if(x<1||y<1||x>n||y>m||a[x][y]==0) continue;
if(!f.orange&&a[x][y]==3) continue;
if(a[f.x][f.y]==4&&check(f)) //处理前一个是4的情况(我直接放在循环内部了)
{
if(i!=f.d) continue; //方向要相同
bool o;
if(a[x][y]==2) o=true;
else o=false;
if(step[x][y][i][o]==-1)
{
step[x][y][i][o]=step[f.x][f.y][i][f.orange]+1; //滑行步数要+1
q.push((Node){x,y,i,o});
}
}
else
{
bool o;
if(a[x][y]==2) o=1;
else if(a[x][y]==4) o=0;
else o=f.orange;
if(step[x][y][i][o]!=-1) continue;
step[x][y][i][o]=step[f.x][f.y][f.d][f.orange]+1;
q.push((Node){x,y,i,o});
}
}
}
int ans=1<<30;
for(int i=0;i<4;i++)
for(int j=0;j<=1;j++)
if(step[n][m][i][j]!=-1)
ans=min(ans,step[n][m][i][j]);
printf("%d",ans==1<<30?-1:ans);
}``````