萌新刚刚学bfs,求助qwq
查看原帖
萌新刚刚学bfs,求助qwq
198719
洛璟楼主2021/3/4 08:54

WA了,只有24分kk

#include<bits/stdc++.h>
using namespace std;
int n, m;
char c[510][510];
int dis[510][510];
int wk[3][3][5];
char ch[10];
deque<pair<int, int> >q;
inline int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c>'9')
    {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        x = (x << 3) + (x << 1) + (c ^ '0');
        c = getchar();
    }
    return x * f;
}
void bfs()
{
    memset(dis, 0x3f, sizeof(dis));
    q.push_front(make_pair(1, 1));
    dis[1][1] = 0;
    while (!q.empty())
    {
        int x = q.front().first, y = q.front().second;
        q.pop_front();
        for (int i = 1;i <= 4;++i)
        {
            int dx1 = x + wk[1][1][i], dy1 = y + wk[1][2][i];
            int dx2 = x + wk[2][1][i], dy2 = y + wk[2][2][i];
            if (dx1 > m || dx1 <= 0 || dy1 > n || dy1 <= 0) continue;
            if (ch[i] != c[dx2][dy2])
            {
                int tmp = dis[x][y] + 1;
                if (tmp < dis[dx1][dy1])
                {
                    q.push_back(make_pair(dx1, dy1));
                    dis[dx1][dy1] = tmp;
                }
            }
            else
            {
                int tmp = dis[x][y];
                if (tmp < dis[dx1][dy1])
                {
                    q.push_front(make_pair(dx1, dy1));
                    dis[dx1][dy1] = tmp;
                }
            }
        }
    }
}
signed main()
{
    wk[1][1][1] = -1;
    wk[1][1][2] = -1;
    wk[1][1][3] = 1;
    wk[1][1][4] = 1;

    wk[1][2][1] = -1;
    wk[1][2][2] = 1;
    wk[1][2][3] = -1;
    wk[1][2][4] = 1;

    wk[2][1][1] = -1;
    wk[2][1][2] = -1;
    wk[2][1][3] = 0;
    wk[2][1][4] = 0;

    wk[2][2][1] = -1;
    wk[2][2][2] = 0;
    wk[2][2][3] = -1;
    wk[2][2][4] = 0;

    ch[1] = '\\';
    ch[2] = '/';
    ch[3] = '/';
    ch[4] = '\\';
    n = read();
    m = read();
    for (int i = 1;i <= n;++i)
    {
        cin >> c[i] + 1;
    }
    if ((n + m) % 2 == 1)
    {
        printf("NO SOLUTION\n");
    }
    bfs();
    printf("%d", dis[n][m]);
    return 0;
}
2021/3/4 08:54
加载中...