求调,玄关
查看原帖
求调,玄关
1113126
Statax楼主2024/10/15 23:31
#include <bits/stdc++.h>

#define endl '\n'
#define lowbit(x) x & (-x)
#define ll long long
#define ull unsigned long long

using namespace std;
const int N = 55 + 5;

int n, m;
bool vis[N][N][4], mapp[N][N];
unordered_map<char, int> umap;
struct point { int x, y, dis, ward; };

pair<int, int> left_up(int x, int y) {
    return make_pair(x, y);
} pair<int, int> left_down(int x, int y) {
    return make_pair(x + 1, y);
} pair<int, int> right_up(int x, int y) {
    return make_pair(x, y + 1);
} pair<int, int> right_down(int x, int y) {
    return make_pair(x + 1, y + 1);
}

void init() {
    umap['S'] = 0, umap['W'] = 1, umap['N'] = 2, umap['E'] = 3;
}

bool isValid(int x, int y, int ward) {
    if(x < 0 || x > n || y < 0 || y > m) return 0;
    if(mapp[left_up(x, y).first][left_up(x, y).second]) return 0;
    if(mapp[left_down(x, y).first][left_down(x, y).second]) return 0;
    if(mapp[right_up(x, y).first][right_up(x, y).second]) return 0;
    if(mapp[right_down(x, y).first][right_down(x, y).second]) return 0;
    if(left_up(x, y).first < 0 || left_up(x, y).first > n || left_up(x, y).second < 0 || left_up(x, y).second > m) return 0;
    if(left_down(x, y).first < 0 || left_down(x, y).first > n || left_down(x, y).second < 0 || left_down(x, y).second > m) return 0;
    if(right_up(x, y).first < 0 || right_up(x, y).first > n || right_up(x, y).second < 0 || right_up(x, y).second > m) return 0;
    if(right_down(x, y).first < 0 || right_down(x, y).first > n || right_down(x, y).second < 0 || right_down(x, y).second > m) return 0;
    return !vis[x][y][ward];
}

// 0 下,1 左,2 上,3 右 
int bfs() {
    char oper;
    int sx, sy, tx, ty;
    cin >> sx >> sy >> tx >> ty >> oper;
    queue<point> q; q.push({sx, sy, 0, umap[oper]});
    while(!q.empty()) {
        auto cur = q.front(); q.pop();
        if(cur.x == tx && cur.y == ty) {
            return cur.dis;
        } if(isValid(cur.x, cur.y, (!cur.ward? 3 : cur.ward - 1))) {
            q.push({cur.x, cur.y, cur.dis + 1, (!cur.ward? 3 : cur.ward - 1)});
            vis[cur.x][cur.y][(!cur.ward? 3 : cur.ward - 1)] = 1;
        } if(isValid(cur.x, cur.y, (cur.ward + 1) % 4)) {
            q.push({cur.x, cur.y, cur.dis + 1, (cur.ward + 1) % 4});
            vis[cur.x][cur.y][(cur.ward + 1) % 4] = 1;
        }
        if(cur.ward == 0) {
            int cnt = 0;
            int x = cur.x, y = cur.y;
            for(; cnt < 3; ++cnt) {
                ++x;
                if(isValid(x, y, cur.ward)) {
                    q.push({x, y, cur.dis + 1, cur.ward});
                    vis[x][y][cur.ward] = 1;
                } else break;
            }
        } else if(cur.ward == 1) {
            int cnt = 0;
            int x = cur.x, y = cur.y;
            for(; cnt < 3; ++cnt) {
                --y;
                if(isValid(x, y, cur.ward)) {
                    q.push({x, y, cur.dis + 1, cur.ward});
                    vis[x][y][cur.ward] = 1;
                } else break;
            }
        } else if(cur.ward == 2) {
            int cnt = 0;
            int x = cur.x, y = cur.y;
            for(; cnt < 3; ++cnt) {
                --x;
                if(isValid(x, y, cur.ward)) {
                    q.push({x, y, cur.dis + 1, cur.ward});
                    vis[x][y][cur.ward] = 1;
                } else break;
            }
        } else if(cur.ward == 3) {
            int cnt = 0;
            int x = cur.x, y = cur.y;
            for(; cnt < 3; ++cnt) {
                ++y;
                if(isValid(x, y, cur.ward)) {
                    q.push({x, y, cur.dis + 1, cur.ward});
                    vis[x][y][cur.ward] = 1;
                } else break;
            }
        } 
    } return -1;
}

int main() {
    // freopen("xxx.in", "r", stdin);
    // freopen("xxx.out", "w", stdout);
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> m;
    for(int i = 1;i <= n; ++i) {
        for(int j = 1;j <= m; ++j) {
            cin >> mapp[i][j];
        }
    } cout << bfs() << endl;
	return 0;
}

2024/10/15 23:31
加载中...