package com.algorithm.algorithm01server.demo;
import java.util.*;
public class Demo5 {
//图论 F 迷宫问题
static int wide, high, step, Row, Col;
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, 1, 0, -1};
static int[][] map;
static int target = 11;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
List list = new ArrayList();
while (true) {
wide = scanner.nextInt();
high = scanner.nextInt();
if (high == 0 || wide == 0) {
break;
}
//二维数组存储邻接矩阵
map = new int[high][wide];
for (int i = 0; i < high; i++) {
for (int j = 0; j < wide; j++) {
map[i][j] = scanner.nextInt();
if (map[i][j] == 2) {
Row = i;
Col = j;
}
}
}
//最开始的地方走了一步
step = 1;
int dfs = dfs(Row, Col, step);
list.add(dfs);
}
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
}
}
private static int dfs(int Row, int Col, int step) {
if (step > 10) {
return -1;
}
//找到返回步数
for (int i = 0; i < 4; i++) {
//走的方向
int nx = Row + dx[i];
int ny = Col + dy[i];
//如果没有碰到墙继续向前走
while (nx >= 0 && nx < high && ny >= 0 && ny < wide && map[nx][ny] != 1) {
if (map[nx][ny] == 3) {
return Math.min(step, target);
}
nx += dx[i];
ny += dy[i];
}
if (nx >= 0 && nx < high && ny >= 0 && ny < wide && map[nx][ny] == 1) {
map[nx][ny] = 0;//碰到石块,坐标的位置标记为0
dfs(nx - dx[i], ny - dy[i], step + 1);//找到石块坐标的前一个位置,然后步数+1
map[nx][ny] = 1;
}
}
//没有找到返回-1
return -1;
}
}
dfs的一个问题,题目大概是:如果遇到的格子是 0空置广场 1是堵塞 2是开始位置 3目标位置,求最小步数问题。
然后我每次输入测试用例的时候都返回的是-1,找了很久没发现问题,请求一下,问问是哪里写错了?
我的测试用例
6 1
1 1 2 1 1 3
0 0