定义一个二维数组 N*M ,如 5 × 5 数组下所示:
int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
它表示一个迷宫,其中的1表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的路线。入口点为[0,0],既第一格是可以走的路。
数据范围: , 输入的内容只包含
定义一个二维数组 N*M ,如 5 × 5 数组下所示:
int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
它表示一个迷宫,其中的1表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的路线。入口点为[0,0],既第一格是可以走的路。
数据范围: , 输入的内容只包含
输入两个整数,分别表示二维数组的行数,列数。再输入相应的数组,其中的1表示墙壁,0表示可以走的路。数据保证有唯一解,不考虑有多解的情况,即迷宫只有一条通道。
左上角到右下角的最短路径,格式如样例所示。
5 5 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0
(0,0) (1,0) (2,0) (2,1) (2,2) (2,3) (2,4) (3,4) (4,4)
5 5 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 1 1 0 0 0 0 0 0
(0,0) (1,0) (2,0) (3,0) (4,0) (4,1) (4,2) (4,3) (4,4)
注意:不能斜着走!!
import java.util.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int m = in.nextInt(); int maze[][] = new int[n][m]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { maze[i][j] = in.nextInt(); } } int[][] seek = new int[n][m];//用于标记坐标点是否背探寻过,如果是探寻过的,则不再搜索 Stack<int[]> ans = new Stack<>();//保存走过的路径 ans.push(new int[]{0, 0});//起点 seek[0][0] = 1; while(true) { int[] lastPos = ans.peek(); //如果探寻的最新的点已经到达右下角,结束 if (lastPos[0] == n - 1 && lastPos[1] == m - 1) break; //依次探寻左,上,右,下,如果四个方向都不可达,回退路径的上一个点重新探寻 if (!canArrived(0, lastPos, ans, maze, seek) && !canArrived(1, lastPos, ans, maze, seek) && !canArrived(2, lastPos, ans, maze, seek) && !canArrived(3, lastPos, ans, maze, seek)) { ans.pop(); } } for (int[] an : ans) { System.out.println("(" + an[0] + "," + an[1] + ")"); } } /** * 判断pos点是否可以向direction方向走是否可达 * @param direction 0:向左,1:向上,2:向右,3:向下 * @param lastPos 当前位置 * @param ans 保存探寻到的路径 * @param maze 迷宫 * @param seek 是否已经探寻过 * @return */ public static boolean canArrived(int direction, int[] lastPos, Stack<int[]> ans, int[][] maze, int[][] seek) { boolean canArrived = false; int[] pos = new int[]{lastPos[0], lastPos[1]}; switch (direction) { case 0: pos[1] -= 1; break; case 1: pos[0] -= 1; break; case 2: pos[1] += 1; break; case 3: pos[0] += 1; break; default: break; } if (pos[0] < 0 || pos[0] >= maze.length || pos[1] < 0 || pos[1] >= maze[0].length) { //越过边界 canArrived = false; } else{ //位置合法,且未被探寻过,且可达 if (seek[pos[0]][pos[1]] != 1 && maze[pos[0]][pos[1]] == 0) { //未被探寻过,且可达 ans.push(pos); canArrived = true; } //该点置为被探寻过 seek[pos[0]][pos[1]] = 1; } return canArrived; } }
import java.util.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int hang = in.nextInt(); int lie = in.nextInt(); int[][] db = new int[hang][lie]; for (int i = 0; i < hang; i++) { for (int j = 0; j < lie; j++) { db[i][j] =in.nextInt(); } } boolean[][] flag = new boolean[hang][lie];//表示位置是否走过 StringBuilder stringBuilder = new StringBuilder(); // dfs( db,0,0, stringBuilder,flag); bfs(db, flag); } private static boolean dfs(int[][] db, int hang, int lie, StringBuilder stringBuilder, boolean[][] flag) { //边界判断 if (hang < 0 || hang >= db.length || lie < 0 || lie >= db[0].length || flag[hang][lie]) { return false; } if (db[hang][lie] == 0) { stringBuilder.append("(" + hang + "," + lie + ")\n"); //出口 if (hang == db.length - 1 && lie == db[0].length - 1) { System.out.println(stringBuilder); return true; } flag[hang][lie] = true;//标记该位置已走过 //尝试该位置下 上下左右位置是否可行 if (dfs(db, hang - 1, lie, stringBuilder, flag) || dfs(db, hang + 1, lie, stringBuilder, flag) || dfs(db, hang, lie - 1, stringBuilder, flag) || dfs(db, hang, lie + 1, stringBuilder, flag)) { //回溯 注意这里回溯两个坐标,因为if判断中有一个是0,但对应的坐标没有没有通路,所以回溯当前坐标跟这个0的坐标 stringBuilder.delete(stringBuilder.length() - 12, stringBuilder.length()); } else { return true; } } return false; } private static void bfs(int[][] db, boolean[][] flag) { int[][] direction = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};//创建方向数组用于遍历 Queue<Point> queue = new LinkedList<>(); queue.add(new Point(0, 0,"(" + 0 + "," + 0 + ")\n"));//初始化 flag[0][0] = true; while (!queue.isEmpty()) { Point point = queue.poll();//获取并删除队列中的第一个元素 int hang = point.hang; int lie = point.lie; //出口 if (hang == db.length - 1 && lie == db[0].length - 1) { System.out.println(point.path); return; } //四个方向遍历 for (int[] ints : direction) { int nx = ints[0] + hang; int ny = ints[1] + lie; Point temp = new Point(nx, ny, point.path); if (nx >= 0 && nx < db.length && ny >= 0 && ny < db[0].length && !flag[nx][ny] && db[nx][ny] == 0) { temp.hang =nx; temp.lie =ny; temp.path = point.path +"(" + nx + "," + ny + ")\n"; queue.add(temp); flag[nx][ny] = true; } } } } } class Point { public int hang; public int lie; public String path; public Point(int hang, int lie,String path) { this.hang = hang; this.lie = lie; this.path =path; } }
import java.util.*; public class T43 { public static void main(String[] args) { int[][] direction = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; HashMap<String, String> father = new HashMap<>(); Scanner sc = new Scanner(System.in); String str = sc.nextLine(); String[] split = str.split(" "); int n = Integer.parseInt(split[0]); int m = Integer.parseInt(split[1]); int[][] grid = new int[n][m]; boolean[][] mark = new boolean[n][m]; mark[0][0] = true; Queue<int[]> queue = new ArrayDeque<>(); queue.add(new int[]{0, 0}); for (int i = 0; i < n; i++) { String tempStr = sc.nextLine(); String[] temp = tempStr.split(" "); for (int j = 0; j < n; j++) { grid[i][j] = Integer.parseInt(temp[j]); } } //BFS while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { int[] point = queue.poll(); int x = point[0]; int y = point[1]; if (x == n - 1 && y == m - 1) { break; } for (int[] ints : direction) { int nx = ints[0] + x; int ny = ints[1] + y; if (nx >= 0 && nx < n && ny >= 0 && ny < m && !mark[nx][ny] && grid[nx][ny] == 0) { queue.add(new int[]{nx, ny}); mark[nx][ny] = true; father.put("(" + nx + "," + ny + ")", "(" + x + "," + y + ")"); } } } } Stack<String> result = new Stack<>(); String key = "(" + (n - 1) + "," + (m - 1) + ")"; result.add(key); while (true) { String tempstr = father.get(key); key = tempstr; result.add(tempstr); if (key.equals("(0,0)") ) { break; } } while (!result.isEmpty()) { System.out.println(result.pop()); } } }
import java.util.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { static String res; //最终结果 public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int m = in.nextInt(); // 构造迷宫 int[][] arr = new int[n][m]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { arr[i][j] = in.nextInt(); } } StringBuilder path = new StringBuilder(); //初始坐标 0,0 backTrack(arr, 0, 0, path); System.out.println(res); } // 递归回溯 private static void backTrack(int[][] arr, int x, int y, StringBuilder path) { //跃出边界或者点位不为0则返回 if (x < 0 || x >= arr.length || y < 0 || y >= arr[0].length || arr[x][y] != 0) { return; } //走到了最右下点位 if (x == arr.length - 1 && y == arr[0].length - 1) { path.append("(" + x + "," + y + ")\n"); res = path.toString(); return; } //标记为已走过 arr[x][y] = 1; path.append("(" + x + "," + y + ")\n"); backTrack(arr, x, y - 1, path); //向上 backTrack(arr, x, y + 1, path); //向下 backTrack(arr, x - 1, y, path); //向左 backTrack(arr, x + 1, y, path); //向右 //回退 path.delete(path.length() - 6, path.length()); arr[x][y] = 0; } }
import java.util.*; public class HJ43 { public static void main(String[] args) { Scanner in = new Scanner(System.in); // 注意 hasNext 和 hasNextLine 的区别 while (in.hasNextInt()) { int n = in.nextInt(); int m = in.nextInt(); int[][] datas = new int[n][m]; List<Point> points = new ArrayList<>(); // set用来去重,检查过的点不需要再检查 Set<String> duplicateSet = new HashSet<>(); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { datas[i][j] = in.nextInt(); } } // 深度遍历datas,遇到0的就是通路,遇到1就是墙壁 for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { deepDatas(datas, i, j, points, duplicateSet); } } // points是倒序的,反转一下 Collections.reverse(points); points.forEach(it -> System.out.println("(" + it.x + "," + it.y + ")")); } } public static boolean deepDatas(int[][] datas, int x, int y, List<Point> points, Set<String> duplicateSet) { if (x < 0 || y < 0 || x >= datas.length || y >= datas[0].length || datas[x][y] == 1) { return false; } if (!duplicateSet.add(x + ":" + y)) { return false; } if (x == datas.length - 1 && y == datas[0].length - 1) { points.add(new Point(x, y)); return true; } boolean deepResult; deepResult = deepDatas(datas, x + 1, y, points, duplicateSet); deepResult = deepResult || deepDatas(datas, x - 1, y, points, duplicateSet); deepResult = deepResult || deepDatas(datas, x, y - 1, points, duplicateSet); deepResult = deepResult || deepDatas(datas, x, y + 1, points, duplicateSet); if (deepResult) { points.add(new Point(x, y)); } return deepResult; } public static class Point { public int x; public int y; public Point(int x, int y) { this.x = x; this.y = y; } } }
import java.util.*; public class Main { private static List<int[]> list = new ArrayList<>(); private static boolean[][] flag; private static boolean win = false; private static void dfs(int[][] arr,int i,int j){ // 不符合条件 if (arr[i][j]==1||flag[i][j]){ return; } // 找到出口 if (i==arr.length-1&&j==arr[0].length-1){ list.add(new int[]{i,j}); win = true; return; } if(!win) list.add(new int[]{i,j}); flag[i][j] = true; if (i>0){ dfs(arr,i-1,j); } if (i< arr.length-1){ dfs(arr,i+1,j); } if (j>0){ dfs(arr,i,j-1); } if (j<arr[0].length-1){ dfs(arr,i,j+1); } if (!win){ list.remove(list.size()-1); } } public static void main(String[] args){ Scanner sc = new Scanner(System.in); int m = sc.nextInt(); int n = sc.nextInt(); int[][] arr = new int[m][n]; for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ arr[i][j] = sc.nextInt(); } } flag = new boolean[m][n]; dfs(arr,0,0); for (int i = 0; i < list.size(); i++) { System.out.println("("+list.get(i)[0]+","+list.get(i)[1]+")"); } } }
public class Test01 { //定义全局变量,用来收集结果 static StringBuffer sb = new StringBuffer(); public static void main(String[] args) { Scanner in = new Scanner(System.in); while (in.hasNextInt()) { int[][] arr = new int[in.nextInt()][in.nextInt()]; for (int i = 0; i < arr.length; i++) { for (int j = 0; j < arr[0].length; j++) { arr[i][j] = in.nextInt(); } } dfs(arr,0,0,""); System.out.println(sb.toString()); } } public static boolean dfs(int[][] arr,int i ,int j,String result){ //下标越界 if(i>arr.length-1||j>arr[0].length-1||i<0||j<0){ return false; } //走出迷宫,使用全局变量收集结果。 if(i==arr.length-1 && j==arr[0].length-1){ sb.append(result); sb.append("("+i+","+j+")"); return true; } //如果为0,表示可以走 if(arr[i][j]==0){ //标记已走过的路 arr[i][j]=2; //result回溯结果 if(dfs(arr,i-1,j,result+"("+i+","+j+")\n")){ return true; } if(dfs(arr,i+1,j,result+"("+i+","+j+")\n")){ return true; } if(dfs(arr,i,j-1,result+"("+i+","+j+")\n")){ return true; } if(dfs(arr,i,j+1,result+"("+i+","+j+")\n")){ return true; } //回溯 arr[i][j]=0; } return false; } }
import java.util.Scanner; import java.util.*;; public class Main { public int x; public int y; public Main parent; public void setValue(int x, int y, Main parent) { this.x = x; this.y = y; this.parent = parent; } public static boolean bfs(ArrayList<Main> zt, LinkedList<Main> open, int maze[][], int N, int M, int[][] visit) { while (!open.isEmpty()) {//节点的上下左右只是open的一部分 int posX = open.get(0).x; int posY = open.get(0).y; zt.add(open.get(0));//close表存储路径 if (posX == (N - 1) && posY == (M - 1)) { return true; } for (int i = -1; i < 2; i++) for (int j = -1; j < 2; j++) { if (i != j && i != -1 * j) {//满足条件的i,j组合为{-1,0},{0,-1},{1,0},{0,1},即上下左右四个方向 posX = open.get(0).x + i; posY = open.get(0).y + j; if (posX < N && posX >= 0 && posY < M && posY >= 0) { if (maze[posX][posY] == 0 && visit[posX][posY] == 0 ) { Main migongtemp = new Main(); migongtemp.setValue(posX, posY, open.get(0)); visit[posX][posY] = 1; open.add(migongtemp); } } } } open.remove(0); } return false; } public static void printRoad(ArrayList<Main> zt) { ArrayList<String> road = new ArrayList(); Main migongtemp = zt.get(zt.size() - 1); //向前追溯路径 while (migongtemp.parent != null) { road.add("(" + migongtemp.x + "," + migongtemp.y + ")"); migongtemp = migongtemp.parent; } if (migongtemp.parent == null) { road.add("(" + migongtemp.x + "," + migongtemp.y + ")"); } //向后打印 for (int i = road.size() - 1; i > 0; i--) { System.out.println(road.get(i)); } System.out.println(road.get(0)); } public static void main(String args[]) { Scanner scan = new Scanner(System.in); int[][] maze = new int[11][11]; int[][] visit = new int[11][11]; while (scan.hasNext()) { ArrayList<Main> zt = new ArrayList ();//就是close 表,存路径 LinkedList<Main> open = new LinkedList ();//bfs遍历表,存当前待遍历节点,LinkedList好删除头节点,Queue是基于LinkedList int N = scan.nextInt(); int M = scan.nextInt(); for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { maze[i][j] = scan.nextInt(); } } for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { visit[i][j] = maze[i][j]; } } Main migongtemp = new Main(); migongtemp.setValue(0, 0, null); open.add(migongtemp); if (bfs(zt, open, maze, N, M, visit)) { printRoad(zt); } } } }
import java.util.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); // 注意 hasNext 和 hasNextLine 的区别 while (in.hasNextInt()) { // 注意 while 处理多个 case int n = in.nextInt(); int m = in.nextInt(); int[][] map = new int[n][m]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { map[i][j] = in.nextInt(); } } List<Position> path = new ArrayList<>(); if(dfs(path, map, 0, 0)) { for (Position p : path) { System.out.println("(" + p.x + "," + p.y + ")"); } } } } public static boolean dfs(List<Position> path, int[][] map, int x, int y) { int n = map.length; int m = map[0].length; if (x < 0 || y < 0 || x >= n || y >= m) { return false; } if (map[x][y] == 1) return false; if (x == n - 1 && y == m - 1) { path.add(new Position(x, y)); return true; } path.add(new Position(x, y)); map[x][y] = 1; if (dfs(path, map, x + 1, y)) return true; if (dfs(path, map, x, y + 1)) return true; if (dfs(path, map, x - 1, y)) return true; if (dfs(path, map, x, y - 1)) return true; path.remove(path.size() - 1); map[x][y] = 0; return false; } public static class Position{ int x; int y; public Position(int x, int y) { this.x = x; this.y = y; } } }
static LinkedList<Integer[]> goList = new LinkedList<>(); static Integer[][] arr; public static void main(String[] args) { Scanner in = new Scanner(System.in); // 注意 hasNext 和 hasNextLine 的区别 while (in.hasNext()) { // 注意 while 处理多个 case int widh = in.nextInt(); int height = in.nextInt(); arr = new Integer[height][widh]; for (int i = 0; i < widh; i ++) { for (int j = 0; j < height; j ++) { arr[j][i] = in.nextInt(); } } LinkedList<Integer[]> myList = new LinkedList<>(); myList.add(new Integer[] {0, 0}); getPath(myList); while(!goList.isEmpty()){ Integer[] integers = goList.removeFirst(); System.out.printf("(%s,%s)",integers[1],integers[0]); System.out.println(); } } } public static void getPath(LinkedList<Integer[]> list) { Integer[] postion = list.getLast(); if(postion[0] == arr.length-1 && postion[1] == arr[0].length-1 && (list.size()<goList.size() || goList.isEmpty())){ goList = list; return; } // 向右 Integer[] newPostion = null; if (postion[0]<arr.length-1 && isValid(list, newPostion = new Integer[] {postion[0] + 1, postion[1]})) { LinkedList<Integer[]> myList = new LinkedList<>(list); myList.add(newPostion); getPath(myList); } // 向左 if (postion[0]>0 && isValid(list, newPostion = new Integer[] {postion[0] - 1, postion[1]})) { LinkedList<Integer[]> myList = new LinkedList<>(list); myList.add(newPostion); getPath(myList); } // 向上 if (postion[1]>0 && isValid(list, newPostion = new Integer[] {postion[0] , postion[1]-1})) { LinkedList<Integer[]> myList = new LinkedList<>(list); myList.add(newPostion); getPath(myList); } // 向下 if (postion[1]<arr[0].length-1 && isValid(list, newPostion = new Integer[] {postion[0], postion[1] + 1})) { LinkedList<Integer[]> myList = new LinkedList<>(list); myList.add(newPostion); getPath(myList); } } public static boolean isValid(LinkedList<Integer[]> list, Integer[] newPostion) { return arr[newPostion[0]][newPostion[1]] != 1 && !list.stream().anyMatch(item -> item[0] == newPostion[0] && item[1] == newPostion[1]); }
运行时间:19ms 超过88.64% 用Java提交的代码 占用内存:9628KB 超过93.21% 用Java提交的代码
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.LinkedList; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] mazeSize = br.readLine().split(" "); int n = Integer.parseInt(mazeSize[0]), m = Integer.parseInt(mazeSize[1]); int[][] maze = new int[n][m]; for (int i = 0; i < n; i++) { String[] inputs = br.readLine().split(" "); for (int j = 0; j < m; j++) { maze[i][j] = Integer.parseInt(inputs[j]); } } Solution sl = new Solution(); System.out.println(sl.findPath(maze, n, m)); } } class Solution { int n, m; int[][] maze; int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; public StringBuilder findPath(int[][] maze, int n, int m) { this.n = n; this.m = m; this.maze = maze; boolean[][] visited = new boolean[n][m]; LinkedList<Integer> path = new LinkedList<>(); dfs(path, visited, 0, 0); int size = path.size(); StringBuilder sb = new StringBuilder(); for (int i = 0; i < size; i++) { sb.append("(").append(path.get(i++)).append(", ").append(path.get(i)).append(")\n"); } return sb; } public void dfs(LinkedList<Integer> path, boolean[][] visited, int row, int col) { path.add(row); path.add(col); visited[row][col] = true; if (row == n - 1 && col == m - 1) { return; } for (int[] dir : dirs) { int nr = row + dir[0], nc = col + dir[1]; if (nr >= 0 && nc >= 0 && nr < n && nc < m && !visited[nr][nc] && maze[nr][nc] == 0) { dfs(path, visited, nr, nc); if (visited[n - 1][m - 1]) { return; } path.removeLast(); path.removeLast(); } } } }
//思路很清晰 迷宫 递归回溯 import java.util.*; public class Main { public static List<List<Integer>> list = new ArrayList<>();//所有通关通道 public static LinkedList<Integer> path = new LinkedList<>();//其中一条通道 public static boolean[][] flag;//判断是否走过 public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); //构建迷宫 int m = sc.nextInt();//行数 int n = sc.nextInt();//列数 int[][] arr = new int[m][n]; flag = new boolean[m][n]; for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ arr[i][j] = sc.nextInt(); } } int res = m * n;//结果的长度 find(arr, 0, 0);//递归回溯查找 int k = 0;//记录最短路径的下标 //找到最短的路径 for (int i = 0; i < list.size(); i++) { if (res < list.get(i).size()) { res = list.get(i).size();//更新 k = i; } } //输出结果 for(int i = 0; i < list.get(k).size(); i += 2){ System.out.println("(" + list.get(k).get(i) +"," + list.get(k).get(i + 1) + ")"); } } //递归回溯 找出所有安全通道 public static void find(int[][] arr, int i, int j){ //越界或者走过或者有墙,返回 if (i < 0 || i >= arr.length || j < 0 || j >= arr[0].length || arr[i][j] == 1 || flag[i][j] == true) { return; } //通关则加入 if(i == arr.length - 1 && j == arr[0].length - 1){ path.add(i); path.add(j); list.add(new ArrayList<>(path)); } //上下左右,遍历 flag[i][j] = true; path.add(i); path.add(j); find( arr, i + 1, j); find( arr, i - 1, j); find( arr, i, j + 1); find( arr, i, j - 1); flag[i][j] = false; path.removeLast(); path.removeLast(); } }
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class Main { static boolean[][] fg; static List<Pair> path = new ArrayList<>(); static List<Pair> res; static int r,c; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String str1 = null; String[] ss = br.readLine().split(" "); r = Integer.parseInt(ss[0]); c = Integer.parseInt(ss[1]); int[][] map = new int[r][c]; fg = new boolean[r][c]; int k = 0; while(k < r && (str1 = br.readLine()) != null){ String[] sc = str1.split(" "); for(int i = 0;i < sc.length;i++){ map[k][i] = Integer.parseInt(sc[i]); } k++; } path.add(new Pair(0,0)); fg[0][0] = true; dfs(map,0,0); for(int i = 0;i < res.size();i++){ int a = res.get(i).x; int b = res.get(i).y; System.out.println("(" + a + "," + b + ")"); } } public static void dfs(int[][] map,int x,int y){ if(x == r - 1 && y == c - 1){ res = new ArrayList<>(path); return; } if(x + 1 <= r - 1 && x + 1 >= 0 && !fg[x + 1][y] && map[x + 1][y] == 0){ path.add(new Pair(x + 1,y)); fg[x + 1][y] = true; dfs(map,x + 1,y); path.remove(path.size() - 1); fg[x + 1][y] = false; } if(x - 1 <= r - 1 && x - 1 >= 0 && !fg[x - 1][y] && map[x - 1][y] == 0){ path.add(new Pair(x - 1,y)); fg[x - 1][y] = true; dfs(map,x - 1,y); path.remove(path.size() - 1); fg[x - 1][y] = false; } if(y + 1 <= c - 1 && y + 1 >= 0 && !fg[x][y + 1] && map[x][y + 1] == 0){ path.add(new Pair(x,y + 1)); fg[x][y + 1] = true; dfs(map,x,y + 1); path.remove(path.size() - 1); fg[x][y + 1] = false; } if(y - 1 <= c - 1 && y - 1 >= 0 && !fg[x][y - 1] && map[x][y - 1] == 0){ path.add(new Pair(x,y - 1)); fg[x][y - 1] = true; dfs(map,x,y - 1); path.remove(path.size() - 1); fg[x][y - 1] = false; } } } class Pair{ public int x; public int y; Pair(int x,int y){ this.x = x; this.y = y; } }
import java.util.*; public class Main { static List<String> op = new ArrayList<>(); public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); int[] mi[] = new int[n][m]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { mi[i][j] = sc.nextInt(); } } List<String> str = new ArrayList<>(); str.add("(0,0)"); boolean[][] v = new boolean[n][m]; v[0][0] = true; dfs(mi, 0, 0, str, v); for (int i = 0; i < op.size(); i++) { System.out.println(op.get(i)); } } public static void dfs(int[][] mi, int n, int m, List<String> str, boolean[][] v) { if (mi.length == n + 1 && mi[0].length == m + 1) { op = str; return; } if (n + 1 < mi.length && mi[n + 1][m] == 0 && v[n + 1][m] == false) { v[n + 1][m] = true; List<String> str1 = new ArrayList<>(str); str1.add("(" + (n + 1) + "," + m + ")"); dfs(mi, n + 1, m, str1, v); } if (n - 1 >= 0 && mi[n - 1][m] == 0 && v[n - 1][m] == false) { v[n - 1][m] = true; List<String> str2 = new ArrayList<>(str); str2.add("(" + (n - 1) + "," + m + ")"); dfs(mi, n - 1, m, str2, v); } if (m + 1 < mi[0].length && mi[n][m + 1] == 0 && v[n][m + 1] == false) { v[n][m + 1] = true; List<String> str3 = new ArrayList<>(str); str3.add("(" + n + "," + (m + 1) + ")"); dfs(mi, n, m + 1, str3, v); } if (m - 1 >= 0 && mi[n][m - 1] == 0 && v[n][m - 1] == false) { v[n][m - 1] = true; List<String> str4 = new ArrayList<>(str); str4.add("(" + n + "," + (m - 1) + ")"); dfs(mi, n, m - 1, str4, v); } } }
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; /** * @author YXQ * @create 2022/8/3 15:31 */ public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String str1 = br.readLine(); int n=Integer.parseInt(str1.split(" ")[0]); int m=Integer.parseInt(str1.split(" ")[1]); int[][] arr=new int[n][m]; for(int i=0;i<n;i++){ String[] temp=br.readLine().split(" "); for (int j=0;j<m;j++){ arr[i][j]=Integer.parseInt(temp[j]); } } boolean[][] flag=new boolean[n][m]; dfs(arr,0,0,flag); for(int[] aixs:res){ System.out.println("("+aixs[0]+","+aixs[1]+")"); } } static List<int[]> path=new ArrayList<>(); static List<int[]> res=new ArrayList<>(); public static void dfs(int[][] arr,int i,int j,boolean[][] flag){ if(i==arr.length-1&&j==arr[0].length-1&&arr[i][j]==0){ path.add(new int[]{i,j}); if(res.size()==0||res.size()>path.size())res=new ArrayList<>(path); return; } if(i<0||j<0||i>arr.length-1||j>arr[0].length-1||arr[i][j]==1||flag[i][j])return; flag[i][j]=true; path.add(new int[]{i,j}); dfs(arr,i+1,j,flag); dfs(arr,i,j+1,flag); dfs(arr,i-1,j,flag); dfs(arr,i,j-1,flag); path.remove(path.size()-1); flag[i][j]=false; } }
public class Main { private static final List<String> pathList = new LinkedList<>(); public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] arr = br.readLine().split(" "); int m = Integer.parseInt(arr[0]); int n = Integer.parseInt(arr[1]); boolean[][] maze = new boolean[m][n]; String[] split; for (short i = 0; i < m; i ++) { split = br.readLine().split(" "); for (short j = 0; j < n; j++) { maze[i][j] = split[j].equals("0"); } } boolean[][] visited = new boolean[m][n]; search(maze, m, n, 0, 0, visited); for(String path : pathList) { System.out.println(path); } } private static boolean search(boolean[][] maze, int m, int n, int i, int j, boolean[][] visited) { // 标记当前坐标为已访问 visited[i][j] = true; // 如果是终点 if (i == m - 1 && j == n - 1) { pathList.add(0, "(" + i + "," + j + ")"); return true; } // 寻找合法的可进入坐标 int newI = -1, newJ = -1; boolean accessable = false; // go up if (i - 1 >= 0 && maze[i - 1][j] && !visited[i - 1][j]) { newI = i - 1; newJ = j; accessable = search(maze, m, n, newI, newJ, visited); if (accessable) { pathList.add(0, "(" + i + "," + j + ")"); return true; } } // go down if (i + 1 < m && maze[i + 1][j] && !visited[i + 1][j]) { newI = i + 1; newJ = j; accessable = search(maze, m, n, newI, newJ, visited); if (accessable) { pathList.add(0, "(" + i + "," + j + ")"); return true; } } // go left if (j - 1 >= 0 && maze[i][j - 1] && !visited[i][j - 1]) { newI = i; newJ = j - 1; accessable = search(maze, m, n, newI, newJ, visited); if (accessable) { pathList.add(0, "(" + i + "," + j + ")"); return true; } } // go right if (j + 1 < n && maze[i][j + 1] && !visited[i][j + 1]) { newI = i; newJ = j + 1; accessable = search(maze, m, n, newI, newJ, visited); if (accessable) { pathList.add(0, "(" + i + "," + j + ")"); return true; } } // 哪里都无法走 return false; } }