poj 2935 bfs

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<queue> #include<stack> using namespace std; const int maxn=15; int dir[maxn][maxn],map[maxn][maxn][4],sx,sy,ex,ey; int help[4][2]={1,0,0,1,-1,0,0,-1}; char s[4]={'S','E','N','W'}; typedef struct {int x,y;}node; void init() { memset(map,0,sizeof(map)); memset(dir,-1,sizeof(dir)); } void solve() { queue<node> que; node tp={sx,sy}; dir[sx][sy]=0; que.push(tp); while(que.size()) { node tmp=que.front(); que.pop(); for(int i=0;i<4;i++) { node tpp={tmp.x+help[i][0],tmp.y+help[i][1]}; if(tpp.x>=1&&tpp.x<=6&&tpp.y>=1&&tpp.y<=6&&dir[tpp.x][tpp.y]==-1&&!map[tmp.x][tmp.y][i]) { que.push(tpp); dir[tpp.x][tpp.y]=i; if(tpp.x==ex&&tpp.y==ey) return; } } } } void prinf() { stack<int> stc; node now={ex,ey}; while(!(now.x==sx&&now.y==sy)) { int tp=dir[now.x][now.y]; stc.push(tp); tp=(tp+2)%4; now.x+=help[tp][0]; now.y+=help[tp][1]; } while(stc.size()) { printf("%c",s[stc.top()]); stc.pop(); } printf("\n"); } int main() { int tx1,ty1,tx2,ty2; while(scanf("%d%d",&sy,&sx)!=EOF&&(sx||sy)) { scanf("%d%d",&ey,&ex); if(sx==ex&&sy==ey) {printf("\n");continue;} init(); for(int i=1;i<=3;i++) { scanf("%d%d%d%d",&ty1,&tx1,&ty2,&tx2); if(tx1==tx2) { if(ty1>ty2) swap(ty1,ty2); while(ty1<ty2) { map[tx1][ty1+1][0]=map[tx1+1][ty1+1][2]=1; ty1++; } } else { if(tx1>tx2) swap(tx1,tx2); while(tx1<tx2) { map[tx1+1][ty1][1]=map[tx1+1][ty1+1][3]=1; tx1++; } } } solve(); prinf(); } return 0; }