poj 2935 (bfs+路径)
#include<cstdio>#include<cstring>#include<queue>#define swap(a,b) a^=b^=a^=b using namespace std;const int maxn = 15;const int dir[4][2]={0,2,2,0,0,-2,-2,0};const char ch[4]={'E','S','W','N'};struct node {int x,y;int pre;char c;}q[maxn*maxn];int sx,sy,ex,ey,num;int mp[maxn][maxn];bool iswall( int x,int y,int i){if ( i==0 && mp[x][y-1] ) return true;else if(i==1&&mp[x-1][y]) return true;else if(i==2&&mp[x][y+1]) return true;else if(i==3&&mp[x+1][y]) return true;else return false;}void print(int x){if(x) {print(q[x].pre );printf("%c",q[x].c);}}void bfs( ){int front = 0, rear = 0;node frm = {sx,sy,0,0};q[rear++] = frm;while(front < rear){frm = q[front];for( int i=0;i<4;i++){node to = {frm.x+dir[i][0],frm.y+dir[i][1],front,ch[i]};if(to.x < 2||to.x >12||to.y <2||to.y > 12) continue;if(!mp[to.x][to.y]&&!iswall(to.x,to.y,i)){mp[to.x][to.y] = 1; q[rear] = to;if(to.x==ex&&to.y==ey) {print( rear );//printf("\nrear = %d front = %d",rear,front);return ;}++rear;}}++front;} }int main(){int a1,a2,b1,b2;while(scanf("%d%d",&sy,&sx)&&(sx||sy)){scanf("%d%d",&ey,&ex);memset(mp,0,sizeof(mp));ex = 2*ex;ey = 2*ey;sx = 2*sx;sy = 2*sy;mp[sx][sy] = 1;for(int i=0;i<3;i++){scanf("%d%d%d%d",&b1,&a1,&b2,&a2);if( a1 == a2 ){if(b1>b2) swap(b1,b2);for(int j=b1;j<b2;j++)mp[a1*2+1][j*2+2]=1;}else {if(a1>a2) swap(a1,a2);for(int j=a1;j<a2;j++)mp[2*j+2][b1*2+1]=1;}}if( sx==ex && sy ==ey ){puts("");continue;} bfs();printf("\n");}return 0;}
?
