博客

问题描述:

嘿嘿~这个游戏大家都玩过吧。本题是自己给定一张地图和炸弹的初始位置，炸弹位置可移动，现在你需要移动炸弹是炸弹能够炸掉最多的敌人，炸弹一次可以炸掉一行和一列但是墙可以挡住炸弹。
给定的地图中#代表墙，G代表敌人，. 代表炸弹可以移动的地方，保证结果唯一。

输入:

第一行输入炸弹起始位置坐标，第二行输入地图大小n、m（n，m<=10）。
第三到3+n行输入地图。

样例输入:

3 1
6 8
# # # # # # # #
# G G . G G G .
# # # . # G # G
# . . . . . . .
# G # . # # G G
# # G . . . . G

样例输出:

1,3
5

问题分析:

用DFS(深度优先)算法，对炸弹人能到达的位置进行遍历(find函数)，每到达一个位置，将当前位置坐标传入Boom函数进行爆破，计算每一个位置能炸掉的敌人并记录，并将消灭的最多的敌人数返回到find函数记录到变量Max，实时更新消灭敌人最多的位置的坐标。经过的位置用符号’*’标记。

实现代码：

#include<bits/stdc++.h>
using namespace std;
char Map[100][100];
int m,n,X,Y;
int Max=0; 
int Boom(int x,int y){
	int i = 1;
	int sum = 0;
	while(Map[x+i][y]!='#'&&x+i<n){
		if(Map[x+i][y]=='G')
			sum++;
		i++;
	}
	i = 1;
	while(Map[x-i][y]!='#'&&x-i>=0){
		if(Map[x-i][y]=='G')
			sum++;
		i++;
	}
	i = 1;
	while(Map[x][y+i]!='#'&&y+i<m){
		if(Map[x][y+i]=='G')
			sum++;
		i++;
	}
	i = 1;
	while(Map[x][y-i]!='#'&&y-i>=0){
		if(Map[x][y-i]=='G')
			sum++;
		i++;
	}
	return sum;
}
void find(int x,int y){
	int number = Boom(x,y);
	if(number>Max)
	{
		Max = number;
		Y = y;
		X = x;
	}
	Map[x][y] = '*';
	if(Map[x+1][y]=='.'&&x+1<n)
		find(x+1,y);
	if(Map[x][y+1]=='.'&&y+1<m)
		find(x,y+1);
	if(Map[x-1][y]=='.'&&x-1>=0)
		find(x-1,y);
	if(Map[x][y-1]=='.'&&y-1>=0)
		find(x,y-1);
}
int main()
{
	int x,y;
	cin>>x>>y>>n>>m;
	fill(Map[0],Map[0]+100*100,'#');
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			cin>>Map[i][j];
		}
	}
	find(x,y);
	cout<<X<<","<<Y<<endl;
	cout<<Max;
	return 0;
}