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){Scannersc=newScanner(System.in);n=sc.nextInt();m=sc.nextInt();sc.nextLine();maze=newchar[n][m];if(n==1&&m==1){System.out.print("Yes");return;}for(inti=0;i<n;i++){maze[i]=sc.nextLine().trim().toCharArray();}visited=newboolean[n][m];// 3. 初始化访问标记数组（全部默认为 false）visited=newboolean[n][m];// 4. 从起点 (0,0) 开始DFS搜索dfs(0,0);// 5. 输出结果：能到终点输出 Yes，否则 NoSystem.out.println(reach?"Yes":"No");}publicstaticvoiddfs(intx,inty){//走出来迷宫，修改值并且返回if(x==n-1&&y==m-1){reach=true;return;}//对于走过的值先标记visited[x][y]=true;//然后开始通过深度优先逐层开始找// // 上下左右四个方向：上、下、左、右//static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};//遍历上下左右for(int[]d:dir){intnx=x+d[0];intny=y+d[1];//这时候得到了坐标，判断能不能走通// ④ 判断下一步能不能走// 条件：// 1. 不出界// 2. 是空地 .// 3. 没走过if(nx>=0&&nx<n&&ny>=0&&ny<m&&maze[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){Scannersc=newScanner(System.in);n=sc.nextInt();m=sc.nextInt();sc.nextLine();grid=newchar[n][m];visited=newboolean[n][m];//录入字符for(inti=0;i<n;i++){grid[i]=sc.nextLine().trim().toCharArray();}intcount=0;//寻找水坑for(inti=0;i<n;i++){for(intj=0;j<m;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){//加横坐标intnx=x+dir[0];intny=y+dir[1];if(nx>=0&&nx<n&&ny>=0&&ny<m&&grid[nx][ny]=='W'&&!visited[nx][ny]){dfs(nx,ny);}}}}
