Home  >  Q&A  >  body text

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都错,,我也太渣了,请高手赐教!!

黄舟黄舟2764 days ago529

reply all(1)I'll reply

  • PHP中文网

    PHP中文网2017-04-17 15:37:58

    Looking at the example is not a search at all.

    As long as the position of "Headquarters" is not higher than the given "water release" position, it will be flooded.

    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';
        }
    }

    reply
    0
  • Cancelreply