炸彈人問題

問題描述：小人可以在迷宮中任意地方放置一個炸彈，炸彈可以在以該點為中心的十字方向殺死怪物，但是觸碰到墻之后不再能傳遞攻擊。求將一個炸彈放在哪個位置可以殺死更多的怪物？？

Input：

13 13 ############# #GG.GGG#GGG.# ###.#G#G#G#G# #.......#..G# #G#.###.#G#G# #GG.GGG.#.GG# #G#.#G#.#.#.# ##G...G.....# #G#.#G###.#G# #...G#GGG.GG# #G#.#G#G#.#G# #GG.GGG#G.GG# ############# 3 3

Output:
7 11 10
即（7， 11）坐標處可以殺死10個怪物

思路一：遍歷圖中的每個點，若非墻壁，怪物則計算該點可以殺死多少怪物，循環遍歷，找出最大之（注：但是，不幸的是，這樣的的方法對于一些特殊的點不適用，例如圖中的（1，11）點）

思路二：BFS/DFS，先篩選出可以抵達的點，再計算

DFS

package Bomberman;import java.util.Scanner;public class DFS {static char[][] a = new char[20][20];static int[][] book = new int[20][20];static Scanner input = new Scanner(System.in);static int max = 0;static int mx, my;static int n, m;public static void main(String[] args) {n = input.nextInt();m = input.nextInt();for (int j = 0; j < n; j++) {String str = input.next();a[j] = str.toCharArray();}int startX = input.nextInt();int startY = input.nextInt();book[startX][startY] = 1;max = getsum(startX, startY);mx = startX;my = startY;dfs(startX, startY);System.out.println(mx + " " + my + " " + max);}public static void dfs(int x, int y) {/*** 右、下、左、上* */int sum, tx, ty;int[][] next = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};sum = getsum(x, y);if (sum > max) {max = sum;mx = x;my = y;}for (int i = 0; i < 4; i++) {tx = x + next[i][0];ty = y + next[i][1];if (tx < 0 || tx > n - 1 || ty < 0 || ty > m - 1) {continue;}if (a[tx][ty] == '.' && book[tx][ty] == 0) {book[tx][ty] = 1;dfs(tx, ty);}}return;}public static int getsum(int i, int j) {int x, y;int sum = 0;x = i;y = j;while (a[x][y] != '#') {if (a[x][y] == 'G') {sum++;}x--;}x = i;y = j;while (a[x][y] != '#') {if (a[x][y] == 'G') {sum++;}x++;}x = i;y = j;while (a[x][y] != '#') {if (a[x][y] == 'G') {sum++;}y--;}x = i;y = j;while (a[x][y] != '#') {if (a[x][y] == 'G') {sum++;}y++;}return sum;} }

---

BFS

import java.util.LinkedList; import java.util.Queue; import java.util.Scanner;class note {int x;int y;note(int x, int y) {this.x = x;this.y = y;} } public class BFS {static char[][] a = new char[20][20];static int[][] book = new int[20][20];static Queue<note> queue = new LinkedList<>();static Scanner input = new Scanner(System.in);static int n, m;static int max=0, mx, my;public static void main(String[] args) {/*** "#"代表墻，"G"代表怪物，"."代表放置炸彈的位置* */n = input.nextInt();m = input.nextInt();for (int l = 0; l < n; l++) {String str = input.next();a[l] = str.toCharArray();}int startX = input.nextInt();int startY = input.nextInt();queue.offer(new note(startX, startY));max = getnum(startX, startY);mx = startX;my = startY;bfs();System.out.println(mx + " " + my + " " + max);}public static void bfs() {int tx, ty, sum;int[][] next = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};while (!queue.isEmpty()) {for (int l = 0; l < 4; l++) {tx = queue.peek().x + next[l][0];ty = queue.peek().y + next[l][1];if (tx < 0 || tx > n - 1 || ty < 0 || ty > m - 1) {continue;}if (a[tx][ty] == '.' && book[tx][ty] == 0) {book[tx][ty] = 1;queue.offer(new note(tx, ty));sum = getnum(tx, ty);if (sum > max) {max = sum;mx = tx;my = ty;}}}queue.remove();}}/*** 獲取在某點放置炸彈可以殺死的怪物數* */public static int getnum(int i, int j) {int sum, x, y;sum = 0;x = i;y = j;while (a[x][y] != '#') {if (a[x][y] == 'G') {sum++;}x--;}x = i;y = j;while (a[x][y] != '#') {if (a[x][y] == 'G') {sum++;}x++;}x = i;y = j;while (a[x][y] != '#') {if (a[x][y] == 'G') {sum++;}y--;}x = i;y = j;while (a[x][y] != '#') {if (a[x][y] == 'G') {sum++;}y++;}return sum;} }

總結

以上是生活随笔為你收集整理的搜索算法（二）--DFS/BFS求解炸弹人问题（JAVA ）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。