给出6*6的矩阵，，起点，终点，一共三堵墙，墙不会相交。
求起点到终点的最少步，保证有解
对每次移动判断相对应的是否有墙即可
#include "stdio.h"#include "string.h"#include "queue"using namespace std;const int dir[4][2]={ {1,0},{-1,0},{0,1},{0,-1} };int wall[10][10][10][10];int s_x,s_y,e_x,e_y;int used[10][10];struct node{int x,y;};void pri(int x,int y){if (used[x][y]==0) return ;if (used[x][y]==1){pri(x-1,y);printf("S");}if (used[x][y]==2){pri(x+1,y);printf("N");}if (used[x][y]==3){pri(x,y-1);printf("E");}if (used[x][y]==4){pri(x,y+1);printf("W");}}void bfs(){queue<node>q;node cur,next;int i;cur.x=s_x;cur.y=s_y;q.push(cur);memset(used,-1,sizeof(used));used[cur.x][cur.y]=0;while (!q.empty()){cur=q.front();q.pop();for (i=0;i<4;i++){next.x=cur.x+dir[i][0];next.y=cur.y+dir[i][1];if (next.x<=0 || next.x>6 || next.y<=0 || next.y>6) continue;if (i==0 && wall[cur.x][cur.y-1][cur.x][cur.y]==1) continue;if (i==1 && wall[next.x][next.y-1][next.x][next.y]==1) continue;if (i==2 && wall[cur.x-1][cur.y][cur.x][cur.y]==1) continue;if (i==3 && wall[next.x-1][next.y][next.x][next.y]==1) continue;if (used[next.x][next.y]!=-1) continue;used[next.x][next.y]=i+1;q.push(next);if (next.x==e_x && next.y==e_y){pri(next.x,next.y);printf("\n");return ;}}}}int main(){int i,j,x1,x2,y1,y2,temp;while (scanf("%d%d",&s_y,&s_x)!=EOF){if (s_x+s_y==0) break;scanf("%d%d",&e_y,&e_x);memset(wall,0,sizeof(wall));for (i=1;i<=3;i++){scanf("%d%d%d%d",&y1,&x1,&y2,&x2);if (x1==x2){if (y1>y2) {temp=y1; y1=y2; y2=temp;}for (j=y1;j<y2;j++)wall[x1][j][x1][j+1]=1;}else{if (x1>x2) {temp=x1; x1=x2; x2=temp;}for (j=x1;j<x2;j++)wall[j][y1][j+1][y1]=1;}}bfs();}return 0;}
你可能付出一定的代价，但日后你得到的，远比付出的多得多。
