题目描述:
示例:
注意 : 不能斜着走
解题思路:
dfs(深度优先搜索)+回溯 (用栈)进行上下左右搜索回溯
代码 :
package homeWork;
import java.util.Scanner;
import java.util.Stack;
class Point{
int x;
int y;
public Point(int x,int y){
this.x=x;
this.y=y;
}
}
public class dfs {
private static int rows;
private static int cols;
private static Stack<Point> stack=new Stack<>();
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
while (scanner.hasNext()){
rows=scanner.nextInt();
cols=scanner.nextInt();
int[][] map=new int[rows][cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
map[i][j]=scanner.nextInt();
}
}
mazePath(map,0,0);
}
}
private static void mazePath(int[][] map, int x, int y) {
Point p=new Point(x,y);
stack.push(p);
map[x][y]=1;
if (x==rows-1 && y==cols-1){
for (Point point:stack){
System.out.println("("+point.x+","+point.y+")");
}
}
if (x+1<rows && map[x+1][y]==0){ //下
mazePath(map,x+1,y);
}
if (y+1<cols && map[x][y+1]==0){ //右
mazePath(map,x,y+1);
}
if (x-1>=0 && map[x-1][y]==0){ //上
mazePath(map,x-1,y);
}
if (y-1>=0 && map[x][y-1]==0){ //左
mazePath(map,x,y-1);
}
map[x][y]=0;
stack.pop(); //回溯
}
}
- over ✨
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)