这为什么会错啊
查看原帖
这为什么会错啊
609967
kuokuo楼主2022/4/27 21:02
#include <iostream>
#include <unordered_map>
#include <cstring>
#include <deque>
#define l first
#define r second

using namespace std;

typedef pair<int,int> PII;
const int N = 500;
char draw[N][N];
int dist[N][N];
bool st[N][N];
int t, n, m;
deque<PII> q;

int bfs()
{
    int dx[4] = {-1, -1, 1, 1}, dy[4] = {-1, 1, 1, -1};
    int ix[4] = {-1, -1, 0, 0}, iy[4] = {-1, 0, 0, -1};
    memset(st, 0, sizeof st);
    memset(dist, 0x3f, sizeof dist);
    char cs[] = "\\/\\/";
    q.push_back({0,0});
    dist[0][0] = 0;
    while(q.size())
    {
        PII t = q.front();
        q.pop_front();
        
        if(st[t.l][t.r]) continue;
        st[t.l][t.r] = true;
        
        for (int i = 0; i < 4; ++i)
        {
            int x = t.l + dx[i], y = t.r + dy[i];
            if(x < 0 || x > n || y < 0 || y > m) continue;
            int gx = t.l + ix[i], gy = t.r + iy[i];

            int d = dist[t.l][t.r] + (draw[gx][gy] != cs[i]);
            if(d < dist[x][y])
            {
                dist[x][y] = d;
                if(!(draw[gx][gy] != cs[i])) q.push_front({x,y});
                else q.push_back({x,y});
            }
        }
    }
    return dist[n][m];
}

int main()
{
        cin >> n >> m;
        for (int i = 0; i < n; ++i) scanf("%s",draw[i]);

        if((n + m) & 1) cout << "NO SOLUTION" << endl;
        else cout << bfs() << endl;
    return 0;
}
2022/4/27 21:02
加载中...