【Codeforces 173B】 B. Chamber of Secrets

https://codeforces.com/problemset/problem/173/B

题意 + 分析

来自 \(OI-wiki\)

这题主要难度就是读题...还有注意初始方向！！！

代码

\(01bfs\)

// LUOGU_RID: 99397081
#include <bits/stdc++.h>

using namespace std;
const int N = 1005, inf = 1e9;
int n, m, dis[N][N][4];
char a[N][N];
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

struct Node {
    int x, y, dir;
};

bool Range (int x, int y) {
    if (x < 1 || x > n || y < 1 || y > m)   return false;
    return true;
}

int main () {
    deque<Node> q;
    cin >> n >> m;
    memset (dis, 0x3f, sizeof dis);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }

    q.push_front ({n, m, 2});
    dis[n][m][2] = 0;
    while (!q.empty ()) {
        auto t = q.front ();
        q.pop_front ();
        int x = t.x, y = t.y, dir = t.dir;
        int dist = dis[x][y][dir];
        //cout << dist << ' ';
        
        int xx = x + dx[dir], yy = y + dy[dir];
        //cout << xx << ' ' << yy << endl;
        if (Range (xx, yy)) {
            if (dist < dis[xx][yy][dir])    q.push_front ({xx, yy, dir}); //不变方向
            dis[xx][yy][dir] = min (dis[xx][yy][dir], dist);
        }
        if (a[x][y] == '#') {
            for (int i = 0; i < 4; i++) {
                if (i == dir)   continue;
                if (dist + 1 < dis[x][y][i])    q.push_back ({x, y, i}); //变方向
                dis[x][y][i] = min (dis[x][y][i], dist + 1);
            } 
        }
    }

    // for (int i = 1; i <= n; i++) {
    //     for (int j = 1; j <= m; j++) {
    //         for (int k = 0; k < 4; k++)    cout << dis[i][j][k] << ' ';
    //         cout << endl;
    //     }
    //     cout << endl;
    // }
    
    if (dis[1][1][2] == 0x3f3f3f3f)     dis[1][1][2] = -1;
    cout << dis[1][1][2] << endl;   
}

//注意初始方向