64分求助奆佬!!!
查看原帖
64分求助奆佬!!!
1308662
Tiks_code楼主2024/3/26 17:38
#include <bits/stdc++.h>

using namespace std;

const int N = 600;

int n, m;

char g[N][N];

int dx[] = { 1,-1,-1,1 };
int dy[] = { 1,1,-1,-1 };
char a[] = "\\/\\/";
int ix[] = { 0,-1,-1,0 };
int iy[] = { 0,0,-1,-1 };

int vis[N][N];

struct node {
    int x, y;
};

deque<node>d;

void bfs() {
    memset(vis, 0x3f3f3f3f, sizeof(vis));
    d.push_back(node{ 1,1 });
    vis[1][1] = 0;
    while (!d.empty()) {
        auto u = d.front();
        d.pop_front();
        int x = u.x, y = u.y;
        for (int i = 0; i < 4; i++) {
            int tx = x + dx[i];
            int ty = y + dy[i];
            int inx = x + ix[i];
            int iny = y + iy[i];
            if (tx < 1 || tx > n || ty < 1 || ty > m) continue;
            if (a[i] != g[inx][iny]) {
                int t = vis[x][y] + 1;
                if (t < vis[tx][ty]) {
                    d.push_back(node{ tx,ty });
                    vis[tx][ty] = t;
                }       
            }
            else {
                int t = vis[x][y];
                if (t < vis[tx][ty]) {
                    d.push_front(node{ tx,ty });
                    vis[tx][ty] = t;
                }
            }
        }
    }
    cout << vis[n][m] << endl;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for(int j = 1;j <= m ; j++){
            cin >> g[i][j];
        }
    }
    if ((n + m) % 2) cout << "NO SOLUTION" << endl;
    else bfs();
    return 0;
}
2024/3/26 17:38
加载中...