原创
之前用了枚举法解炸弹人，题目详情请看我之前的博客：https://www.cnblogs.com/chiweiming/p/9295262.html
利用枚举法是无视地图布局的，枚举法直接全局搜索地图，一遇到空地就从4个方向统计敌人数目，但是有些空地
被敌人所包围，炸弹人是无法进去的，而这些被敌人包围的点若是能炸死敌人最多的点则结果救就会错误，所以可
以先用广度优先搜索（DFS也可以）搜索出哪些点炸弹人可以到达，然后在可到达的点的基础上统计可炸死敌人数。
不熟悉BFS算法请看我博客：https://www.cnblogs.com/chiweiming/p/9337316.html
Java：
import java.util.*;
public class bomb_Two {
static int n; //行
static int m; //列
static char maze[][]; //存储地图
static int book[][]; //标记
static int x[]; //队列横坐标
static int y[]; //队列纵坐标
static int step[]; //步数
static int max=0; //存储最大敌人数
static int save_x; //存储目标横坐标
static int save_y; //存储目标纵坐标
static void Totall(int x,int y) { //统计可消灭敌人数
int total=0;
int dx=x;
int dy=y;
while(maze[dx][dy]!='#') { //右
if(maze[dx][dy]=='G') {
total++;
}
dy++;
}
dx=x;
dy=y;
while(maze[dx][dy]!='#') { //下
if(maze[dx][dy]=='G') {
total++;
}
dx++;
}
dx=x;
dy=y;
while(maze[dx][dy]!='#') { //左
if(maze[dx][dy]=='G') {
total++;
}
dy--;
}
dx=x;
dy=y;
while(maze[dx][dy]!='#') { //上
if(maze[dx][dy]=='G') {
total++;
}
dx--;
}
if(total>max) {
save_x=x;
save_y=y;
max=total;
}
}
public static void main(String[] args) {
Scanner reader=new Scanner(System.in);
n=reader.nextInt();
m=reader.nextInt();
int start_x=reader.nextInt(); //炸弹人初始位置
int start_y=reader.nextInt();
x=new int[n*m];
y=new int[n*m];
step=new int[n*m];
int dir[][]= {{0,1},{1,0},{0,-1},{-1,0}}; //右、下、左、上
int head=0; //头结点
int tail=0; //尾结点
maze=new char[n][m];
book=new int[n][m];
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;
}
}
Totall(start_x,start_y); //统计初始位置可灭敌数
//初始位置入队列
x[tail]=start_x;
y[tail]=start_y;
step[tail]=0;
book[start_x][start_y]=1;
tail++; //尾指针后移
while(head<=tail) {
for(int i=0;i<4;i++) {
int dx=x[head]+dir[i][0];
int dy=y[head]+dir[i][1];
if(dx<0 || dx>n || dy<0 || dy>m) { //越界判断
continue;
}
if(maze[dx][dy]!='.' || book[dx][dy]==1) { //障碍点和空地判断
continue;
}
//符合条件
x[tail]=dx;
y[tail]=dy;
step[tail]=step[head]+1;
book[dx][dy]=1;
tail++;
Totall(dx,dy); //统计敌人数
}
head++; //出队列
}
System.out.println("("+save_x+","+save_y+")"+" "+max);
}
}12:07:58
2018-07-20