有一个由n*n方阵构成的迷宫（n<15），迷宫中有n*n个房间，有的房间可以通过（用0表示），有的房间不能通过（用1表示），游戏者在迷宫中只能向上下左右四个方向移动，不能斜向移动。求从迷宫的左上角到右下角的最短路径，如果不能通过，则输出-1。
输入格式：
第一行为一个整数n(n<15)。
以下n行，每行各有n个整数，分别为0或1，0表示该房间可以通过，1表示该房间不能通过。
输出格式：
输出一个整数，表示从左上角到右下角的最短距离，如果不能到达，则输出-1.
输入样例：
5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
输出样例：
8
因为没有输入案例，所以只写了输出样例为5的这个迷宫，得到答案有8和12，显然8最小
#include <iostream> using namespace std; int maze[5][5]={{0,1,0,0,0},{0,1,0,1,0},{0,0,0,0,0},{0,1,1,1,0},{0,0,0,1,0}}; int used[5][5]={0}; int direction[4][2]={{-1,0},{0,-1},{0,1},{1,0}}; //上下左右四个方向 int count; bool check(int x,int y){ if(x>=0&&y>=0&&x<=4&&y<=4&&used[x][y]==0){ if(maze[x][y]==0) return true; } return false; } void find(int x,int y){ int i,j; if(x==4&&y==4){ cout<<count<<endl; //输出走的步数 return; }else{ for(i=0;i<4;i++){ if(check(x+direction[i][0],y+direction[i][1])){ count++; used[x+direction[i][0]][y+direction[i][1]]=1; find(x+direction[i][0],y+direction[i][1]); count--; used[x+direction[i][0]][y+direction[i][1]]=0; } } } } int main(){ count=0; used[0][0]=1; find(0,0); return 0; }