深度优先搜索（迷宫寻路）--dfs--模版型的两道题

1.HIGH33 迷宫寻路importjava.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息publicclassMain{// 上下左右四个方向上、下、左、右staticint[][]dir{{-1,0},{1,0},{0,-1},{0,1}};staticboolean[][]visited;// 标记某个位置是否走过防止回头死循环staticchar[][]maze;// 存储迷宫地图staticintn,m;// 迷宫的行数 n列数 mstaticbooleanreach;// 标记是否能到达终点true能到false不能publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);nsc.nextInt();msc.nextInt();sc.nextLine();mazenewchar[n][m];if(n1m1){System.out.print(Yes);return;}for(inti0;in;i){maze[i]sc.nextLine().trim().toCharArray();}visitednewboolean[n][m];// 3. 初始化访问标记数组全部默认为 falsevisitednewboolean[n][m];// 4. 从起点 (0,0) 开始DFS搜索dfs(0,0);// 5. 输出结果能到终点输出 Yes否则 NoSystem.out.println(reach?Yes:No);}publicstaticvoiddfs(intx,inty){//走出来迷宫修改值并且返回if(xn-1ym-1){reachtrue;return;}//对于走过的值先标记visited[x][y]true;//然后开始通过深度优先逐层开始找// // 上下左右四个方向上、下、左、右//static int[][] dir {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};//遍历上下左右for(int[]d:dir){intnxxd[0];intnyyd[1];//这时候得到了坐标判断能不能走通// ④ 判断下一步能不能走// 条件// 1. 不出界// 2. 是空地 .// 3. 没走过if(nx0nxnny0nymmaze[nx][ny].!visited[nx][ny]){//如果符合上述条件继续递归dfs(nx,ny);// ⑥ 已经找到终点了直接退出不用再搜if(reach)return;}}}}2.HIGH34 数水坑importjava.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息publicclassMain{//深度优先的代码// 八连通 上下左右及四条对角线意义下互达则它们属于同一个水坑。staticint[][]dirs{{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{-1,1},{1,-1},{1,1}};staticboolean[][]visited;// 标记某个位置是否走过防止回头死循环staticchar[][]grid;// 存储迷宫地图staticintn,m;// 迷宫的行数 n列数 mpublicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);nsc.nextInt();msc.nextInt();sc.nextLine();gridnewchar[n][m];visitednewboolean[n][m];//录入字符for(inti0;in;i){grid[i]sc.nextLine().trim().toCharArray();}intcount0;//寻找水坑for(inti0;in;i){for(intj0;jm;j){if(grid[i][j]W!visited[i][j]){count;//找到一个大水坑dfs(i,j);}}}System.out.print(count);}staticvoiddfs(intx,inty){//先改标记位visited[x][y]true;//遍历方向for(int[]dir:dirs){//加横坐标intnxxdir[0];intnyydir[1];if(nx0nxnny0nymgrid[nx][ny]W!visited[nx][ny]){dfs(nx,ny);}}}}