晋江市住房和城乡建设网站,制作视频剪辑,做石材的一般用什么网站,营销策划公司排行榜炸弹人问题
问题描述#xff1a;小人可以在迷宫中任意地方放置一个炸弹#xff0c;炸弹可以在以该点为中心的十字方向杀死怪物#xff0c;但是触碰到墙之后不再能传递攻击。求将一个炸弹放在哪个位置可以杀死更多的怪物#xff1f;#xff1f; Input#xff1a;
13 1…炸弹人问题
问题描述小人可以在迷宫中任意地方放置一个炸弹炸弹可以在以该点为中心的十字方向杀死怪物但是触碰到墙之后不再能传递攻击。求将一个炸弹放在哪个位置可以杀死更多的怪物 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 3Output: 7 11 10 即7 11坐标处可以杀死10个怪物
思路一遍历图中的每个点若非墙壁怪物则计算该点可以杀死多少怪物循环遍历找出最大之注但是不幸的是这样的的方法对于一些特殊的点不适用例如图中的111点
思路二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 Queuenote queue new LinkedList();static Scanner input new Scanner(System.in);static int n, m;static int max0, 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;}
}
