BFS。

1 /* 1484 */ 2 #include 
     
       3 #include 
      
        4 #include 
       
         5 #include 
        
          6 #include 
         
           7 #include 
          
            8 using namespace std; 9 10 typedef struct {11 int x, y;12 string s;13 } node_t;14 15 bool m[8][8][4];16 bool visit[8][8];17 char ds[5] = "NSWE";18 int dir[4][2] = {19 -1,0,1,0,0,-1,0,120 };21 22 const int n = 6;23 int bx, by, ex, ey;24 string ans;25 26 void bfs() {27 int x = bx, y = by;28 int i, j, k;29 queue
           
             Q;30 string s;31 node_t nd, tmp;32 33 memset(visit, false, sizeof(visit));34 visit[x][y] = true;35 nd.x = x;36 nd.y = y;37 nd.s = "";38 Q.push(nd);39 40 while (!Q.empty()) {41 nd = Q.front();42 Q.pop();43 for (i=0; i<4; ++i) {44 if (m[nd.x][nd.y][i])45 continue;46 x = nd.x + dir[i][0];47 y = nd.y + dir[i][1];48 if (x<=0 || x>6 || y<=0 || y>6 || visit[x][y])49 continue;50 visit[x][y] = true;51 tmp.x = x;52 tmp.y = y;53 tmp.s = nd.s + ds[i];54 if (x==ex && y==ey) {55 ans = tmp.s;56 return ;57 }58 Q.push(tmp);59 }60 }61 }62 63 int main() {64 int i, j, k;65 int x, y;66 int a, b, c, d;67 68 #ifndef ONLINE_JUDGE69 freopen("data.in", "r", stdin);70 #endif71 72 while (scanf("%d %d",&by,&bx)!=EOF && (by||bx)) {73 scanf("%d %d", &ey, &ex);74 memset(m, false, sizeof(m));75 for (i=0; i<3; ++i) {76 scanf("%d%d%d%d", &a,&b,&c,&d);77 if (b == d) {78 // north & south need to mask79 for (y=a+1; y<=c; ++y) {80 m[b][y][1] = true;81 m[b+1][y][0] = true;82 }83 } else {84 // west & east need to mask85 for (x=b+1; x<=d; ++x) {86 m[x][a][3] = true;87 m[x][a+1][2] = true;88 }89 }90 }91 bfs();92 printf("%s\n", ans.c_str());93 }94 95 return 0;96 }