【回溯】BISHI83 迷宫问题

思路

求解代码

privatestaticList<int[]>path=newArrayList<>();/** * 主方法，处理输入输出并调用回溯算法 * * @param args 命令行参数 * @throws IOException 可能抛出的IO异常 */publicstaticvoidmain(String[]args)throwsIOException{// 创建输入输出缓冲流BufferedReaderbr=newBufferedReader(newInputStreamReader(System.in));PrintWriterout=newPrintWriter(newOutputStreamWriter(System.out));// 读取第一行输入，分割并转换为高度h和宽度wString[]strA=br.readLine().trim().split("\\s+");// 解析网格的高度和宽度inth=Integer.parseInt(strA[0]);intw=Integer.parseInt(strA[1]);// 创建网格数组和访问标记数组int[][]grid=newint[h][w];boolean[][]visited=newboolean[h][w];// 读取网格数据for(inti=0;i<h;i++){// 读取一行输入并分割String[]str=br.readLine().trim().split("\\s+");// 填充网格数据for(intj=0;j<w;j++){grid[i][j]=Integer.parseInt(str[j]);}}// 从起点(0,0)开始回溯backtrack(grid,h,w,0,0,visited);// 输出路径for(int[]pos:path){out.println("("+pos[0]+","+pos[1]+")");}// 刷新并关闭输出流和输入流out.flush();out.close();br.close();}/** * 使用回溯算法在网格中寻找路径 * * @return 如果找到从起点到终点的路径则返回true，否则返回false */privatestaticbooleanbacktrack(int[][]grid,inth,intw,inti,intj,boolean[][]visted){// 检查当前位置是否有效：是否在网格范围内、是否是障碍物、是否已经访问过if(i<0||i>=h||j<0||j>=w||grid[i][j]==1||visted[i][j]){returnfalse;}// 标记当前位置为已访问，并将当前位置添加到路径中visted[i][j]=true;path.add(newint[]{i,j});// 如果当前位置是终点，则返回trueif(i==h-1&&j==w-1){returntrue;}// 定义四个方向：上、下、左、右int[]dx={-1,1,0,0};int[]dy={0,0,-1,1};// 尝试向四个方向移动for(intk=0;k<4;k++){// 递归调用backtrack方法，如果找到路径则返回trueif(backtrack(grid,h,w,i+dx[k],j+dy[k],visted)){returntrue;}}// 如果四个方向都无法继续前进，则回溯：从路径中移除当前位置path.remove(path.size()-1);returnfalse;}