c++ - ACM问题,,高手进！！

问题描述

问 题

题目链接在这里：

https://acm.bnu.edu.cn/bnuoj/...

从网上看的题解都是BFS的，自己写了一个DFS的，总是不对，不知何故，请高手赐教！谢谢了！！

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
int t, m, n;
int map[205][205];
int mark[205][205];
int go[4][2] =
{
    0,1,
    0,-1,
    1,0,
    -1,0
};
void DFS(int a, int b)
{
    for (int i = 0; i < 4; i++)
    {
        int aa = a + go[i][0];
        int bb = b + go[i][1];
        if (aa<1 || aa>m || bb<1 || bb>n)
            continue;
        if (mark[aa][bb] == 1)
        {
            map[aa][bb] = max(map[aa][bb], map[a][b]);
            continue;
        }
        if (map[aa][bb] <= map[a][b])
        {
            mark[aa][bb] = 1;
            map[aa][bb] = map[a][b];
            DFS(aa, bb);
        }
    }
}
int main()
{
    while (scanf("%d", &t) != EOF)
    {
        while (t--)
        {
            scanf("%d%d", &m, &n);
            for (int i = 1; i <= m; i++)
                for (int j = 1; j <= n; j++)
                    scanf("%d", &map[i][j]);
            int mm, nn;
            scanf("%d%d", &mm, &nn);
            int x;
            scanf("%d", &x);
            memset(mark, 0, sizeof(mark));
            while (x--)
            {
                int a, b;
                scanf("%d%d", &a, &b);
                mark[a][b] = 1;
                DFS(a, b);
            }
            if (mark[mm][nn] == 1)
                puts("Yes");
            else
                puts("No");
        }
    }
    return 0;
}

然后我又写了一个BFS，还是不对

#include<stdio.h>
#include<iostream>
#include<queue>
#include<algorithm>
#include<string.h>
using namespace std;
struct state
{
    int x, y;
};
int go[4][2]=
{
    0,1,
    0,-1,
    1,0,
    -1,0
};
int map[205][205];
int mark[205][205];
int m, n;
queue<state> q;
bool BFS(int x, int y)
{
    while (!q.empty())
    {
        state s = q.front();
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int xx = s.x + go[i][0];
            int yy = s.y + go[i][1];
            if (xx<1 || xx>m || yy<1 || yy>n)
                continue;
            if (mark[xx][yy] == 1)
                continue;
            if (map[xx][yy] > map[s.x][s.y])
                continue;
            state tmp;
            tmp.x = xx;
            tmp.y = yy;
            mark[xx][yy] = 1;
            q.push(tmp);            
            if (xx == x && yy == y)
                return true;
        }
    }
    return false;
}
int main()
{
    int t;
    //freopen("my.in", "r", stdin);
    while (scanf("%d", &t) != EOF)
    {
        while (t--)
        {
            scanf("%d%d", &m, &n);
            for (int i = 1; i <= m; i++)
                for (int j = 1; j <= n; j++)
                    scanf("%d", &map[i][j]);
            int mm, nn;
            scanf("%d%d", &mm, &nn);
            int x;
            scanf("%d", &x);
            memset(mark, 0, sizeof(mark));
            while (!q.empty())
                q.pop();
            while (x--)
            {
                int a, b;
                scanf("%d%d", &a, &b);
                mark[a][b] = 1;
                state s;
                s.x = a;
                s.y = b;
                q.push(s);
            }
            if (BFS(mm,nn))
                puts("Yes");
            else
                puts("No");
        }
    }
    return 0;
}

DFS BFS都错，，我也太渣了，请高手赐教！！

解决方案

看样例根本不是搜索吧.

是"司令部"的位置只要不高于给出的"放水"的位置就被淹了.

AC 176ms

#include<iostream>
#include<cstring>
using namespace std;
const int SIZE = (200 + 10);
int g[ SIZE ][ SIZE ];
struct node {
    int x, y;
    node(int t_x = -1, int t_y = -1)
        :x(t_x), y(t_y) { }
}start;
int main() {
    int T;
    cin >> T;
    while (T--) {
        int col, row;
        cin >> row >> col;
        for (int i = 0; i<row; i++)
            for (int j = 0; j<col; j++)
                cin >> g[ i ][ j ];
        int x, y;
        cin >> x>> y;
        start = node(x - 1, y - 1);
        int m;
        cin >> m;
        bool flag = false;
        while (m--) {
            cin >> x >> y;
            if (g[ start.x ][ start.y ] <= g[ x-1 ][ y-1 ])
                flag = true;
        }
        if (flag)cout << "Yes";
        else cout << "No";
        cout << '\n';
    }
}

这篇关于c++ - ACM问题,,高手进！！的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！