Истекло время ожидания при решении проблемы алгоритма с BFS. Однако есть проблема, которая может быть решена с помощью DFS. Почему возникает эта разница?
Задача состоит в том, чтобы рассчитать количество прибывших от (1,1) до (N, N) путем перемещения по горизонтали, вертикали или диагонали.
Потребовалось 1331,0 мс, если проблема была решена с помощью BFS (наихудший случай), и 62,0 мс, когда она была решена с помощью DFS. (Я создал и протестировал 16 * 16 массивов.)
Прикрепите URL-адрес проблемы. (Но, пожалуйста, поймите, что это корейский.)
URL> https://www.acmicpc.net/problem/17070
Я хочу услышать ответ ...
- Я думал, что алгоритм BFS будет быстрее, но почему DFS быстрее?
- BFS медленнее, потому что в очереди много элементов? Я хочу знать точную причину.
Код реализации>
Класс Расположение {
int x;
int y;
int dir;
public Location(int x, int y, int dir) {
super();
this.x = x;
this.y = y;
this.dir = dir;
}
}
публичный класс Main {
static int[][] map;
static int Answer;
static int N;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
map = new int[N + 1][N + 1];
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 1; j <= N; j++)
map[i][j] = Integer.parseInt(st.nextToken());
}
DFS(1, 2, 0);
System.out.println(Answer);
Answer = 0;
BFS(1, 2, 0);
System.out.println(Answer);
br.close();
}
static void DFS(int x, int y, int pre) {
if (x == N && y == N) {
Answer++;
return;
}
if (pre == 0) {
if (y + 1 <= N && map[x][y + 1] == 0)
DFS(x, y + 1, 0);
if (y + 1 <= N && map[x][y + 1] == 0 && x + 1 <= N && map[x + 1][y] == 0 && map[x + 1][y + 1] == 0)
DFS(x + 1, y + 1, 1);
} else if (pre == 1) {
if (y + 1 <= N && map[x][y + 1] == 0)
DFS(x, y + 1, 0);
if (x + 1 <= N && map[x + 1][y] == 0)
DFS(x + 1, y, 2);
if (y + 1 <= N && map[x][y + 1] == 0 && x + 1 <= N && map[x + 1][y] == 0 && map[x + 1][y + 1] == 0)
DFS(x + 1, y + 1, 1);
} else {
if (x + 1 <= N && map[x + 1][y] == 0)
DFS(x + 1, y, 2);
if (y + 1 <= N && map[x][y + 1] == 0 && x + 1 <= N && map[x + 1][y] == 0 && map[x + 1][y + 1] == 0)
DFS(x + 1, y + 1, 1);
}
}
static void BFS(int startX, int startY, int dir) {
ArrayDeque<Location> arrayDeque = new ArrayDeque<>();
arrayDeque.add(new Location(startX, startY, dir));
Location location;
int x, y, pre;
while(!arrayDeque.isEmpty()) {
location = arrayDeque.remove();
x = location.x;
y = location.y;
pre = location.dir;
if(x == N-1 && y == N-1) {
Answer++; continue;
}
if (pre == 0) {
if (y + 1 <= N && map[x][y + 1] == 0)
arrayDeque.add(new Location(x, y + 1, 0));
if (y + 1 <= N && map[x][y + 1] == 0 && x + 1 <= N && map[x + 1][y] == 0 && map[x + 1][y + 1] == 0)
arrayDeque.add(new Location(x + 1, y + 1, 1));
} else if (pre == 1) {
if (y + 1 <= N && map[x][y + 1] == 0)
arrayDeque.add(new Location(x, y + 1, 0));
if (x + 1 <= N && map[x + 1][y] == 0)
arrayDeque.add(new Location(x + 1, y, 2));
if (y + 1 <= N && map[x][y + 1] == 0 && x + 1 <= N && map[x + 1][y] == 0 && map[x + 1][y + 1] == 0)
arrayDeque.add(new Location(x + 1, y + 1, 1));
} else {
if (x + 1 <= N && map[x + 1][y] == 0)
arrayDeque.add(new Location(x + 1, y, 2));
if (y + 1 <= N && map[x][y + 1] == 0 && x + 1 <= N && map[x + 1][y] == 0 && map[x + 1][y + 1] == 0)
arrayDeque.add(new Location(x + 1, y + 1, 1));
}
}
}
}