团战可以输、提莫必须死

野性酷女 2022-07-12 07:45 140阅读 0赞

think:  
1广度优先搜索+最值情况判断  
2以结构体数组为基础的队列思想  
3反思:一开始自己用自己不成熟的枚举思想判断最值情况，然后一直wrong anser，调试了一下午也没有找到问题所在，感觉有点浮躁，慢慢的稳稳地，脚踏实地，不要急于求成

[sdut原题链接][sdut]

团战可以输、提莫必须死  
Time Limit: 1000MS Memory Limit: 65536KB

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”.

Example 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

Example Output  
Teemo: 3 3  
BOOM

Hint

Author

以下为accepted代码

#include <stdio.h>
    #include <string.h>
    struct node
    {
        int x;
        int y;
        int amount;
    }link[10016], t, f;
    int map[104][104], vis[104][104];
    int tp, op, n, m, k;
    int xy[4][2] = {
       {
       0, 1}, {
       0, -1}, {-1, 0}, {
       1, 0}};
    void Ans(int X, int Y)
    {
        link[tp].x = X;
        link[tp].y = Y;
        link[tp].amount = 1;
        tp++;
        vis[X][Y] = 1;
        while(op < tp)
        {
            f = link[op++];
            if(f.amount == k)
            {
                printf("Teemo: %d %d\n", f.x, f.y);
                return;
            }
            ///vis[f.x][f.y] = 1;
            int Max = 0, flag = 0;
            for(int i = 0; i < 4; i++)
            {
                if(map[f.x+xy[i][0]][f.y+xy[i][1]] > Max)
                    Max = map[f.x+xy[i][0]][f.y+xy[i][1]];
            }
            for(int i = 0; i < 4; i++)
            {
                t.x = f.x + xy[i][0];
                t.y = f.y + xy[i][1];
                if(t.x > 0 && t.x <= n && t.y > 0 && t.y <= m && vis[t.x][t.y] == 0 && Max == map[t.x][t.y])
                {
                    flag = 1;
                    t.amount = f.amount + 1;
                    link[tp++] = t;
                    vis[f.x][f.y] = 1;
                }
            }
            if(flag == 0)
            {
                printf("BOOM\n");
                return;
            }
        }
        printf("BOOM\n");
    }
    int main()
    {
        while(scanf("%d %d %d", &n, &m, &k) != EOF)
        {
            memset(map, 0, sizeof(map));
            memset(vis, 0, sizeof(vis));
            for(int i = 1; i <= n; i++)
                for(int j = 1; j <= m; j++)
                    scanf("%d", &map[i][j]);
            int a, b;
            scanf("%d %d", &a, &b);
            Ans(a, b);
        }
        return 0;
    }
    
    
    /***************************************************
    User name: 
    Result: Accepted
    Take time: 140ms
    Take Memory: 204KB
    Submit time: 2017-02-16 18:58:27
    ****************************************************/

以下为wrong answer代码

#include <stdio.h>
    #include <string.h>
    #define Max(a, b) (a > b? a: b)
    struct node
    {
        int x;
        int y;
    }link[10000], ans;
    int n, m, k, x1, y1, x2, y2, tp, op, flag;
    int map[100][100], visit[100][100];
    //int jn[] = { -1, 1, 0, 0};
    //int jm[] = { 0, 0, -1, 1};
    int jn[] = {
       0, 0, -1, 1};
    int jm[] = {
       1, -1, 0, 0};
    void ANS()
    {
        int tn1, tn2, tn3, tn4, tm1, tm2, tm3, tm4;
        link[tp].x = x1-1;
        link[tp].y = y1-1;
        tp++;
        flag++;
        visit[x1-1][y1-1] = 1;
        while(op < tp)
        {
            if(flag == k)
                break;
            ans = link[op++];
            tn1 = ans.x + jn[0], tm1 = ans.y + jm[0];
            tn2 = ans.x + jn[1], tm2 = ans.y + jm[1];
            tn3 = ans.x + jn[2], tm3 = ans.y + jm[2];
            tn4 = ans.x + jn[3], tm4 = ans.y + jm[3];
            if(tn1 < 0 || tm1 < 0 || tn1 >= n || tm1 >= m)
                map[tn1][tm1] = -1;
            if(tn2 < 0 || tm2 < 0 || tn2 >= n || tm2 >= m)
                map[tn2][tm2] = -1;
            if(tn3 < 0 || tm3 < 0 || tn3 >= n || tm3 >= m)
                map[tn3][tm3] = -1;
            if(tn4 < 0 || tm4 < 0 || tn4 >= n || tm4 >= m)
                map[tn4][tm4] = -1;
            //printf("map1:%d\n", map[tn1][tm1]);
            //printf("map2:%d\n", map[tn2][tm2]);
            //printf("map3:%d\n", map[tn3][tm3]);
            //printf("map4:%d\n", map[tn4][tm4]);
            if(map[tn1][tm1] >= map[tn2][tm2] && map[tn1][tm1] >= map[tn3][tm3] && map[tn1][tm1] >= map[tn4][tm4] && visit[tn1][tm1] == 0)
            {
                //printf("tn1:%d tm1:%d\n", tn1, tm1);
                link[tp].x = tn1;
                link[tp].y = tm1;
                tp++;
                visit[tn1][tm1] = 1;
                flag++;
                if(flag == k)
                {
                    x2 = tn1;
                    y2 = tm1;
                    break;
                }
            }
            else if(map[tn2][tm2] >= map[tn1][tm1] && map[tn2][tm2] >= map[tn3][tm3] && map[tn2][tm2] >= map[tn4][tm4] && visit[tn2][tm2] == 0)
            {
                //printf("tn2:%d tm2:%d\n", tn2, tm2);
                link[tp].x = tn2;
                link[tp].y = tm2;
                tp++;
                visit[tn2][tm2] = 1;
                flag++;
                if(flag == k)
                {
                    x2 = tn2;
                    y2 = tm2;
                    break;
                }
            }
            else if(map[tn3][tm3] >= map[tn1][tm1] && map[tn3][tm3] >= map[tn2][tm2] && map[tn3][tm3] >= map[tn4][tm4] && visit[tn3][tm3] == 0)
            {
                //printf("tn3:%d tm3:%d\n", tn3, tm3);
                link[tp].x = tn3;
                link[tp].y = tm3;
                tp++;
                visit[tn3][tm3] = 1;
                flag++;
                if(flag == k)
                {
                    x2 = tn3;
                    y2 = tm3;
                    break;
                }
            }
            else if(map[tn4][tm4] >= map[tn1][tm1] && map[tn4][tm4] >= map[tn2][tm2] && map[tn4][tm4] >= map[tn3][tm3] && visit[tn4][tm4] == 0)
            {
                //printf("tn4:%d tm4:%d\n", tn4, tm4);
                link[tp].x = tn4;
                link[tp].y = tm4;
                tp++;
                visit[tn4][tm4] = 1;
                flag++;
                if(flag == k)
                {
                    x2 = tn4;
                    y2 = tm4;
                    break;
                }
            }
            //printf("map1:%d\n", map[tn1][tm1]);
            //printf("map2:%d\n", map[tn2][tm2]);
            //printf("map3:%d\n", map[tn3][tm3]);
            //printf("map4:%d\n", map[tn4][tm4]);
            //printf("visit[tn1][tm1]:%d\n", visit[tn1][tm1]);
            //printf("visit[tn2][tm2]:%d\n", visit[tn2][tm2]);
            //printf("visit[tn3][tm3]:%d\n", visit[tn3][tm3]);
            //printf("visit[tn4][tm4]:%d\n", visit[tn4][tm4]);
        }
        //printf("flag:%d\n", flag);
        if(flag == k)
            printf("Teemo: %d %d\n", x2+1, y2+1);
        else
            printf("BOOM\n");
    }
    int main()
    {
        while(scanf("%d %d %d", &n, &m, &k) != EOF)
        {
            flag = 0;
            tp = op = 0;
            memset(map, 0, sizeof(map));
            memset(visit, 0, sizeof(visit));
            for(int i = 0; i < n; i++)
            {
                for(int j = 0; j < m; j++)
                {
                    scanf("%d", &map[i][j]);
                }
            }
            scanf("%d %d", &x1, &y1);
            //printf("k:%d\n", k);
            if(k == 1)
                printf("Teemo: %d %d\n", x1, x2);
            else
                ANS();
        }
        return 0;
    }
    
    
    /***************************************************
    User name: 
    Result: Wrong Answer
    Take time: 140ms
    Take Memory: 196KB
    Submit time: 2017-02-16 17:47:29
    ****************************************************/

[sdut]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2012/pid/3526