1.问题描述

 我们都直到小霸王游戏中的炸弹人。现在有一个特殊的关卡如下：只有一个炸弹，请问在哪里放置这个炸弹才可以消灭最多的敌人？

我们先把这个地图模型化，用”#“表示墙，这种墙是不可以被炸掉的。敌人用“G“表示，用”.“表示空地：

############# #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# #############

 

2.算法设计 

 1.首先我们用一个二维数组存储这个地图，至于炸弹放置在哪一个点可以消灭最多的敌人，我们需要一个一个来尝试。

2.炸弹的爆炸方向是上下左右四个方向，因此我们在对每一个点进行枚举的时候，需要沿着上下左右四个方向分别统计可以消灭的数目。最终输出消灭最多敌人的那个点。

while(graph[x][y]!='#')//只要没有到边界 { if(graph[x][y]=='G')//是敌人 { sum++;//增加消灭数 } x--;//继续向上寻找 }

3.源代码 

 

#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cstring> using namespace std; const int N =111; //地图最大大小 int main() { char graph[N][N];//存储地图的二维矩阵 int n;//有多少行 int m;//有多少列 int p;//记录放置炸弹x坐标 int q;//记录放置炸弹y坐标 int sum;//记录最多消灭敌人个数 int maxx=0; int x; int y; cout << "请输入地图的行n和列m" << endl; cin >> n >> m; cout << "请输入地图：" << endl; for(int i=0; i<=n-1; i++) { cin >> graph[i]; } for(int i=0; i<=n-1; i++) { for(int j=0; j<=m-1; j++) { if(graph[i][j]=='.') //判断此时位置是否是平地 { sum=0;//初始化最大消灭敌人数是0 //将坐标i，j复制到新变量x，y中，以便上下左右统计可以消灭地人数 x=i; y=j; while(graph[x][y]!='#')//只要没有到边界 { if(graph[x][y]=='G')//是敌人 { sum++;//增加消灭数 } x--;//继续向上寻找 } x=i; y=j; while(graph[x][y]!='#')//只要没有到边界 { if(graph[x][y]=='G')//是敌人 { sum++;//增加消灭数 } x++;//继续向上寻找 } x=i; y=j; while(graph[x][y]!='#')//只要没有到边界 { if(graph[x][y]=='G')//是敌人 { sum++;//增加消灭数 } y--;//继续向上寻找 } x=i; y=j; while(graph[x][y]!='#')//只要没有到边界 { if(graph[x][y]=='G')//是敌人 { sum++;//增加消灭数 } y++;//继续向上寻找 } if(sum>maxx) { maxx=sum; p=i; q=j; } } } } cout << "将炸弹放置在" <<"("<<p<<","<<q<< ")" <<"最多可以消灭" << sum << "个敌人"<< endl; return 0; }

 

4.测试结果