各位神犇,萌新刚学OI求助

回复帖子

@华年 2020-02-14 19:48 回复

RT
题目是这个
这个bfs,我起初以为也没啥,但是第一次交得了51分..日常打脸
后来改了一下,还是不对,用的是第二个数据点
我百思不得其解 决定用手debug一下
debug的图如下:
debug
我亲眼看着他走了一遍,无解
图中绿点是已经走过的点,红点是当先走过的点(当然就上图来说是bfs的终点)
然后我又从出口开始走,反推,发现,最终要走 用红色圈起来的那个点
但是根据题目规则,这点没法走
如果一头奶牛处在这个装置的起点或者终点,这头奶牛就**必须**使用这个装置。
所以不能通过右下的X走到J
当然也可能是我视力不好,看错了?
求各位神犇看一看
下面是最新的源码

#include <queue>
#include <cstdio>
#include <cctype>
#include <string>
#include <iostream>
#define f(x) cout << #x << " : " << (x) << endl;
#define g(x) cout << " " << #x << " ";
#define maxn ( 300 + 5 )

using std::cin;
using std::cout;
using std::endl;
using std::string;

unsigned char map[maxn][maxn];
struct {int x, y; } change[26 * 2];
int n, m, inx, iny;
int loop[maxn][maxn];
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
int bfs(int x, int y);

int main()
{
    scanf("%d %d", &n, &m);
    printf("%d #\n", n);
    for(int i = 1;i <= n;i++)
    {
        scanf("%s", map[i] + 1);
        printf("%s\n", map[i] + 1);
        for(int j = 1;j <= m;j++)
        {
            if(isalpha(map[i][j]))
            {
                map[i][j] = (map[i][j] - 'A') * 2 + 100;
                if(change[map[i][j]].x)
                    map[i][j] ^= 1;
                change[map[i][j]].x = i;
                change[map[i][j]].y = j;
            }
            if(map[i][j] == '@')
                inx = i, iny = j;
        }

    }
    printf("%d", bfs(inx, iny));
    return 0;
}

int bfs(int x, int y)
{
    std::queue<int> q;
    q.push(x);q.push(y);
    map[x][y] = '#';
    int a, b;
    while(!q.empty())
    {
        x = q.front();q.pop();
        y = q.front();q.pop();
        cout << x << " " << y << " " << loop[x][y] << endl;
        if(map[x][y] == '=')
            return loop[x][y];
        if(map[x][y] > 100 && change[map[x][y]].x)
        {
            a = x, b = y;
            // f((unsigned char)((map[a][b] - 100) / 2 + ('A')))
            if(a == change[map[a][b]].x && b == change[map[a][b]].y)
                map[a][b] ^= 1;
            x = change[map[a][b]].x;
            y = change[map[a][b]].y;
            map[a][b] = '#';
            loop[x][y] = loop[a][b];
            cout << x << " " << y << " " << loop[x][y] << endl;
            // f(a)f(b)g( -> )f(x)f(y)
        }
        // g(step)f(loop[x][y])
        for(int i = 0;i < 4;i++)
        {
            if( x + dx[i] < 1 || x + dx[i] > n ||
                y + dy[i] < 1 || y + dy[i] > m)
                continue;
            if(loop[x + dx[i]][y + dy[i]] || map[x + dx[i]][y + dy[i]] == '#')
                continue;
            // f(x + dx[i])f(y + dy[i])
            loop[x + dx[i]][y + dy[i]] = loop[x][y] + 1;
            q.push(x + dx[i]);q.push(y + dy[i]);
        }
        map[x][y] = '#';
    }
    return -55652;
}

另,请忽略代码中额外的输出语句,那是为了配合debug而打的

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。