题目描述

《DFS迷宫遍历》

【DFS迷宫遍历】 有一个3行3列共9个格子的迷宫，从(1,2)格子开始，按照下右上左的顺序进行深度优先搜索，走遍迷宫的9个格子。 #include using namespace std; //访问标记数组,false:没访问过，true：已经访问过 bool visited[4][4]; //方向数组 //4行（4个方向），每两列，0列表示x方向的变化量，1列表示y方向的变化量。 int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1} }; //下右上左 //搜索过的房间数 int cnt=0; //从(x,y)房间开始深度优先搜索 void dfs(int x,int y){ // 终止递归 if(cnt==9) return; //递归搜索(x,y)当前房间的下右上左房间 for(int i = 0;i<4;i++){ int nx = x + dir[i][0]; int ny = y + dir[i][1]; if((nx>=1 && nx<=3 && ny>=1 && ny<=3)&& !visited[nx][ny]){ visited[nx][ny] = true; cnt++; cout<<"("<<nx<<","<<ny<<") "; dfs(nx,ny); } } } int main(){ visited[1][2] = true; cnt++; cout<<"(1,2) "; dfs(1,2); return 0; }

输入格式

无

输出格式

（见样例）