原创
枚举解炸弹人—— https://www.cnblogs.com/chiweiming/p/9295262.html
BFS解炸弹人—— https://www.cnblogs.com/chiweiming/p/9338597.html
关于题目的介绍请看枚举解炸弹人。
由于枚举存在漏洞，所以采用BFS或者DFS来解题。
此篇博客用DFS解炸弹人，不管是DFS还是BFS都是通过这两种算法的全局搜索功能搜索出地图上的每个点，
再在搜索的基础上逐个点统计出敌人数即可。
Java
import java.util.*;
public class bomb_Three {
static int n; //行
static int m; //列
static int save_x;
static int save_y;
static int max=0;
static int dir[][]= {{0,1},{1,0},{0,-1},{-1,0}}; //右、下、左、上
static char maze[][];
static int book[][]; //标记数组
static void Total(int x,int y) { //统计灭敌数
int dx=x;
int dy=y;
int num=0;
while(maze[dx][dy]!='#') { //右
if(maze[dx][dy]=='G') {
num++;
}
dy++;
}
dx=x;
dy=y;
while(maze[dx][dy]!='#') { //下
if(maze[dx][dy]=='G') {
num++;
}
dx++;
}
dx=x;
dy=y;
while(maze[dx][dy]!='#') { //左
if(maze[dx][dy]=='G') {
num++;
}
dy--;
}
dx=x;
dy=y;
while(maze[dx][dy]!='#') { //上
if(maze[dx][dy]=='G') {
num++;
}
dx--;
}
if(num>max) {
max=num;
save_x=x;
save_y=y;
}
}
static void DFS(int x,int y) {
for(int i=0;i<4;i++) {
int dx=x+dir[i][0];
int dy=y+dir[i][1];
if(dx<0 || dx>n || dy<0 || dy>m) {
continue;
}
if(maze[dx][dy]!='.' || book[dx][dy]==1) {
continue;
}
Total(dx,dy);
book[dx][dy]=1;
DFS(dx,dy);
// book[dx][dy]=0; //这里别回溯
}
}
public static void main(String[] args) {
Scanner reader=new Scanner(System.in);
n=reader.nextInt();
m=reader.nextInt();
maze=new char[n][m];
book=new int[n][m];
int start_x=reader.nextInt(); //炸弹人初始位置
int start_y=reader.nextInt();
for(int i=0;i<n;i++) {
String ss=reader.next();
maze[i]=ss.toCharArray();
}
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
book[i][j]=0;
}
}
Total(start_x,start_y);
DFS(start_x,start_y);
System.out.println("("+save_x+","+save_y+")"+" "+max);
}
}测试用例：
输入：
13 13 3 3
#############
#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#
#############
输出：
(7,11) 10
16:06:30
2018-07-20