题意：给你一个图，图上每个点的信息表示该点的水流方向，若下一步走的方向与水流方向一致，则消耗能量为零，否则消耗能量为1，这样，给定起点和终点，问最少消耗的能量。
分析：比赛的时候，一开始交了一个思路很简单的代码，就是用优先队列实现，主要就是标记点的问题了，因为即使使用优先队列，如果当初将一个状态标记为0和1,那么有可能在后面存在“已访问的状态消耗的能量大于即将到达那个状态所消耗的能量”，这样，就无法保证消耗的能量最少了。所以，初始的时候，将每一个状态消耗的能量初始为无穷大，之后，当遇到到达该状态消耗更少能量的，则压入队列。这样就保证了消耗能量最少的问题了。但是，但我把这份很容易敲完的代码叫上去之后，2986ms，这时间虽然是没有TLE，但也差不多算没过了。
该怎么去优化呢？
想了好久，换了一下思路，将代码改了。
这样的，在每次压入一个点的是，我们可以顺便把与该点消耗能量相同的点（就是按照该状态下的水流方向走的点）压入队列，就能保证是先压入的点消耗的能量最少了，同时也就不需要用优先队列了，标记状态也只需要标记为0和1 就够了。
那怎么把能量相同点同时也压入队列呢，其实只需要深搜一下就行了。687ms就过了，但是，如果在找出那些点的过程中不用栈去保存，而是用数组的话，可以再快些。
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
using namespace std;
struct node
{int x,y,energy;
};
bool vis[1001][1001];
char map[1001][1001];
int n,m,ans,si,sj,ei,ej;
int dir[8][2]={{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
stack<node> ST;
void DFS(node temp)
{int k=map[temp.x][temp.y]-'0';int i=temp.x+dir[k][0];int j=temp.y+dir[k][1];node cur;if(i<0||i>=n||j<0||j>=m)return;if(!vis[i][j]){vis[i][j]=true;cur.x=i;cur.y=j;cur.energy=temp.energy;if(i==ei-1 && j==ej-1){ans=temp.energy;return ;}ST.push(cur);DFS(cur);}
}
void BFS()
{queue<node> Q;node f,temp,cur;f.x=si-1;f.y=sj-1;vis[f.x][f.y]=true;f.energy=0;Q.push(f);while(!Q.empty()){temp=Q.front();Q.pop();DFS(temp);while(!ST.empty()){Q.push(ST.top());ST.pop();}if(ans!=-1)return ;for(int k=0;k<8;k++){int i=temp.x+dir[k][0];int j=temp.y+dir[k][1];if(k==map[temp.x][temp.y]-'0')continue;if(i<0||i>=n||j<0||j>=m)continue;if(vis[i][j])continue;vis[i][j]=true;if(i==ei-1 && j==ej-1){ans=temp.energy+1;return ;}cur.x=i;cur.y=j;cur.energy=temp.energy+1;Q.push(cur);DFS(cur);while(!ST.empty()){Q.push(ST.top());ST.pop();}if(ans!=-1)return ;}}
}
int main()
{int k;while(scanf("%d %d",&n,&m)==2){for(int i=0;i<n;i++)scanf("%s",map[i]);scanf("%d",&k);while(k--){memset(vis,0,sizeof(vis));scanf("%d %d %d %d",&si,&sj,&ei,&ej);if(si==ei&&sj==ej){printf("0\n");continue;}ans=-1;BFS();printf("%d\n",ans);}}return 0;
}