团战可以输、提莫必须死

素颜马尾好姑娘i 2022-05-17 08:44 145阅读 0赞

Problem Description

为了一些你们不知道的原因,我们把LOL的地图抽象为一个n×m的矩阵  
提莫积攒了k个蘑菇准备种到地图上去，因为提莫的背篓漏了，所以每一个提莫走过的地方都会被摆下一个蘑菇，两个蘑菇同时种在一个地方的话就会爆炸，所以一旦即将出现这种情况，提莫会直接传送回家，防止自己被炸死  
之前的排位赛中因为乱种蘑菇提莫已经被骂了好多次了，所以这次提莫特地查资料对当前地图的各个位置种下蘑菇的价值做了统计，但是因为提莫行动比较笨拙，所以他每次只能移动到上下左右四个方向的格子中（如果该方向有格子的话  
每次行走提莫会从四个方向挑选一个权值最大的方向，如果有最大的权值有多个，他会从这多个相同的最大权值之中找出没有走过并且按照上下左右的优先顺序挑选一个合适的方向走。如果最大权值都被走过了，他会心灰意冷的传送回家，此时直接输出"BOOM"  
（提莫会顺手在他的起点顺手种一个蘑菇下去

Input

多组输入。  
输入第一行包含地图大小n，m，蘑菇数量k。（1 <= n,m <= 100,1 <= k <= n\*m)  
接下来的n行每行有m个数（并且保证每个数的范围\[1,1e5)  
接下来两个整数x,y代表提莫的起点

Output

如果走到最后没有地方可以种蘑菇了，但蘑菇还没全部种完，输出"BOOM".  
如果蘑菇在半途中种完了，输出提莫所处的坐标"Teemo: x y".

Sample Input

3 3 3
    1 2 3
    4 5 6
    7 8 9
    2 2
    3 3 5
    1 2 3
    4 5 6
    7 8 9
    2 2

Sample Output

Teemo: 3 3
    BOOM

bfs应用，也可以应用dfs

#include<bits/stdc++.h>
    using namespace std;
    int n,m,k,Map[111][111],s1,s2,v[111][111],d[4][2]= {
       {1,0},{-1,0},{0,1},{0,-1}};
    struct node
    {
        int x,y;
        int num;
    }p,q;
    void BFS()
    {
        queue <node> Q;
        int Ma,flag;
        v[s1][s2]=1;
        p.x=s1;
        p.y=s2;
        p.num=1;
        Q.push(p);
        while(!Q.empty())
        {
            q=Q.front();
            Q.pop();
            if(q.num==k)
            {
                cout<<"Teemo: "<<q.x<<" "<<q.y<<endl;
                return;
            }
            Ma=0,flag=0;
            for(int i=0; i<4; i++)
            {
                if(Ma<Map[q.x+d[i][0]][q.y+d[i][1]])
                    Ma=Map[q.x+d[i][0]][q.y+d[i][1]];///找出四个方向权值最大的点；
            }
            for(int i=0; i<4; i++)
            {
                p.x=q.x+d[i][0];
                p.y=q.y+d[i][1];
                p.num=q.num+1;
                if(p.x>=1&&p.x<=n&&p.y>=1&&p.y<=m&&!v[p.x][p.y]&&Map[p.x][p.y]==Ma)
                {
                    flag=1;
                    v[p.x][p.y]=1;
                    Q.push(p);
                }
            }
            if(!flag)
                {cout<<"BOOM"<<endl;return;}
        }
    }
    int main()
    {
        int i,j;
        while(cin>>n>>m>>k)
        {
            memset(v,0,sizeof(v));
            memset(Map,0,sizeof(Map));
            for(i=1; i<=n; i++)//注意:坐标题最好i,j都从1开始
            {
                for(j=1; j<=m; j++)
                {
                    cin>>Map[i][j];
                }
            }
            cin>>s1>>s2;
            BFS();
        }
        return 0;
    }