POJ 1376 bfs

建图的方式有点特别，建在 方格的四个顶点处

vis三维数组，第三维记录走过节点的方向

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#include<map>
const int maxn = 1e2+10;
using namespace std;
int mp[maxn][maxn],n,m,vis[maxn][maxn][4];
int dir[4][2] = {0,1,1,0,0,-1,-1,0};
struct Node{
	int x,y,id,s; 
}st,ed;
bool check(int x,int  y,int id)
{
	return 0  < x && x < n && 0 < y && y < m  && !vis[x][y][id];
}
map<int,char> ma;
int bfs()
{
	queue<Node>Q;
	memset(vis,0,sizeof(vis));
	st.s=0;
	Q.push(st);
	Node now,temp;
	while(!Q.empty()){
		now = Q.front(); Q.pop();
		if(now.x == ed.x && now.y == ed.y){
			return now.s;
		}
		temp = now;temp.s++;
		temp.id = (temp.id+1)%4;
		if(vis[temp.x][temp.y][temp.id]==0){
			vis[temp.x][temp.y][temp.id]=1;Q.push(temp);
		}
		temp = now; temp.s++;
		temp.id = (temp.id-1+4)%4;
		if(vis[temp.x][temp.y][temp.id]==0){
			vis[temp.x][temp.y][temp.id]=1;Q.push(temp);
		} 
		for(int i = 1; i <= 3; ++i){
			temp = now;
			temp.x = now.x+dir[temp.id][0]*i;
			temp.y = now.y+dir[temp.id][1]*i;
			if(mp[temp.x][temp.y]==1) break;
			if(check(temp.x,temp.y,temp.id)){
				temp.s++;
				vis[temp.x][temp.y][temp.id]=1;
				Q.push(temp);
			}
		}
	}

	return -1;
}
int main()
{
	 while(~scanf("%d%d",&n,&m)&& n*m)
	 {
	 	memset(mp,0,sizeof(mp));
	 	for(int i = 0; i < n; ++i)
	 	for(int j = 0; j < m; ++j)
	 	{
	 		int t; scanf("%d",&t);
			if(t) mp[i][j] = mp[i+1][j] = mp[i][j+1] = mp[i+1][j+1] = 1;	
		}
		scanf("%d%d%d%d",&st.x,&st.y,&ed.x,&ed.y);
		char mp[20];
		scanf("%s",mp);
		if(mp[0]=='s') st.id=1;
		else if(mp[0]=='e')st.id=0;
		else if(mp[0]=='w')st.id=2;
		else st.id=3;
		printf("%d\n",bfs());
	 }
}