わかりましたので、この質問http://dwite.ca/questions/shortest_path_around_v2.htmlに取り組み始め、DFS/BFS の 2 つの観点から見ました。ここで、DFS/BFS の両方が機能しない理由を尋ねたいと思います。 BFSとDFSの両方の私のコードです。また、BFSは出力を提供しますが、最短パスではなく、Aパスのみを提供します
package bfsv3;
import java.util.*;
import java.io.*;
public class BFSV3 {
static int steps = 0;
static int numSteps[][] = new int[8][8];
static int finx, finy;
public static void main(String[] args) throws FileNotFoundException {
// here is my input
//........
//........
//...##...
//A..##...
//...##...
//...##...
//...##..B
//........
//and this is the output for the dfs, as you can see where B is it doesnt give 8 but 9
//3 3 3 3 4 5 6 7
//2 2 2 3 4 5 6 7
//1 1 2 # # 5 6 7
//0 1 2 # # 6 6 7
//1 1 2 # # 7 7 7
//2 2 2 # # 8 8 8
//3 3 3 # # 7 8 9
//4 4 4 4 5 6 7 8
Scanner s = new Scanner(new File("C:\\Users\\DANIEL\\Desktop\\Java\\BFSV3\\src\\bfsv3\\DATA4.txt"));
for (int q = 0; q < 5; q++) {
char[][] maze = new char[8][8];
for (int y = 0; y < 8; y++) {
String text = s.nextLine();
for (int x = 0; x < 8; x++) {
maze[x][y] = text.charAt(x);
numSteps[x][y] = 9999;
}
}
for (int z = 0; z < 8; z++) {
for (int a = 0; a < 8; a++) {
if (maze[a][z] == 'B') {
finx = a;
finy = z;
}
if (maze[a][z] == 'A') {
//System.out.println(bfs(maze, z, a, '#', 'B') - 1);
dfs(a, z, maze, 0, 'B');
}
}
}
// System.out.println(finx + " " + finy);
//System.out.println(numSteps[finx][finy]);
for (int i = 0; i < 8; i++) {
for (int a = 0; a < 8; a++) {
if (numSteps[a][i] != 9999) {
System.out.print(numSteps[a][i] + " ");
} else {
System.out.print("#" + " ");
}
}
System.out.println();
}
System.out.println("\n\n");
}
}
public static void dfs(int x, int y, char[][] maze, int steps, char target) {
if (maze[x][y] == '#') {
return;
}
//System.out.println(steps+" "+numSteps[x][y]);
numSteps[x][y] = Math.min(steps, numSteps[x][y]);
if (steps > numSteps[x][y]) {
return;
}
try {
if (x > 0) {
dfs(x - 1, y, maze, steps + 1, target);
}
if (x < 8) {
dfs(x + 1, y, maze, steps + 1, target);
}
if (y > 0) {
dfs(x, y - 1, maze, steps + 1, target);
}
if (y < 8) {
dfs(x, y + 1, maze, steps + 1, target);
}
if (x > 0 && y > 0) {
dfs(x - 1, y - 1, maze, steps + 1, target);
}
if (x > 0 && y < 8) {
dfs(x - 1, y + 1, maze, steps + 1, target);
}
if (x < 8 && y < 8) {
dfs(x + 1, y + 1, maze, steps + 1, target);
}
if (x < 8 && y > 0) {
dfs(x + 1, y - 1, maze, steps + 1, target);
}
} catch (Exception e) {
};
}
public static int bfs(char[][] maze, int yStart, int xStart, char wall, char goal) {
Queue<int[]> queue = new LinkedList<int[]>();
int[] start = {yStart, xStart, 0};
queue.add(start);
while (queue.peek() != null) {
int[] array = queue.remove();
int x = array[0];
int y = array[1];
if (x < 0 || x >= 8 || y < 0 || y >= 8) {
continue;
}
if (maze[x][y] == wall) {
continue;
}
if (maze[x][y] == goal) {
return array[2] + 1;
}
int[][] newPoints = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
//int[][] newPoints = {{-1,-1},{-1,1},{1,-1},{1,1}};
for (int i = 0; i < 8; i++) {
int[] temp = {x + newPoints[i][0], y + newPoints[i][1], array[2] + 1};
queue.add(temp);
}
maze[x][y] = wall;
}
return 0;
}
}