啊哈！算法—枚举之炸弹人

短命女 2022-08-21 12:47 161阅读 0赞

炸弹人：

现有关卡：游戏者只有一枚炸弹，且炸弹可以杀死杀伤范围内所有敌人。请问炸弹放在哪个位置，可以消灭最多的敌人。

思路：

首先将地图模型化。墙用\#表示；敌人用G表示；空地用.表示。炸弹只能放在空地上。

如：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\#  
\#\#\#\#\#\#\#\#\#\#\#\#\#

用一个二维数组存储，一个个尝试各点。炸弹爆炸沿上下左右四个方向，因此进行枚举时，需要沿着上下左右四个方向统计可以消灭的敌人的所有的数目。

如：向下统计：y不变，x每次加1，直到遇到墙为止。

将上下左右四个方向的敌人数相加求和，最终输出消灭敌人数最多的那个空地坐标即可。

#include <iostream>
    using namespace std;
    int main()
    {
        char a[20][21];   //假设地图大小不超过20*20
        int i,j,sum,map=0,p,q,x,y,n,m;
        cin>>n>>m;        //输入行数和列数及各行字符
        for(i=0; i<n; i++)
            for(j=0; j<m; j++)
                cin>>a[i][j];
        for(i=0; i<n; i++)    //两重循环枚举地图每一点
        {
            for(j=0; j<m; j++)
            {
                if(a[i][j]=='.')  //判断是否为平地
                {
                    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++; //继续向右计数
                    }
                    //更新map的值
                    if(sum>map)
                    {
                        map=sum;
                        p=i;   //p、q记录坐标值
                        q=j;
                    }
                }
            }
        }
        cout<<"将炸弹放置在("<<p<<","<<q<<")处，最多可以消灭"<<map<<"个敌人！"<<endl;
        return 0;
    }

运行结果：  
![Center][]

[Center]: /images/20220724/9b97ecfa3f1342afaae7a3359ce42b0c.png