深搜-迷宫
程序员文章站
2022-03-03 11:13:11
...
package aha;
import java.util.Scanner;
public class migong_dfs {
static int n;
static int m;
static int book[][] = new int[51][51];
static int a[][] = new int[51][51];
static int p;
static int q;
static int min = 999;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
a[i][j] = sc.nextInt();
}
}
p = sc.nextInt();
q = sc.nextInt();
book[1][1] = 1;
dfs(1, 1, 0);
System.out.println(min);
}
private static void dfs(int x, int y, int s) {
int tx = 0, ty = 0;
if (p == x && q == y) {
if (min > s) {
min = s;
}
return;
}
int next[][] = {{0,1},{1,0},{0,-1},{-1,0}};//{ { 1, 0 }, { 0,1 }, {-1,0 }, { 0,-1 } };
for (int i = 0; i <= 3; i++) {
tx = x + next[i][0];
ty = y + next[i][1];
if (tx < 1 || tx >n|| ty < 1 || ty > m) {
continue;
}
if(book[tx][ty]==0&&a[tx][ty]==0){
book[tx][ty]=1;
dfs(tx,ty,s+1);
book[tx][ty]=0;
}
}
return ;
}
}/*
5 4
0 0 1 0
0 0 0 0
0 0 1 0
0 1 0 0
0 0 0 1
3 4*/
上一篇: 走迷宫(深搜做法+)