boj #11965

11965.cpp

#include <algorithm>
#include <iostream>
#include <queue>
#include <utility>

using namespace std;

struct point {
    int x, y;
};

using pi = pair<int, bool>;
using pii = pair<point, pi>;

int N, M, arr[1010][1010], visited[1010][1010];
bool purple[1010][1010][4];
int dx[4] = {0, 0, -1, 1}, dy[4] = {1, -1, 0, 0};

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);

    cin >> N >> M;

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> arr[i][j];
        }
    }

    queue<pii> q;
    for (int i = 0; i < 1010; i++) {
        for (int j = 0; j < 1010; j++) {
            visited[i][j] = -1;
        }
    }

    q.push({{1, 1}, {0, false}});
    visited[1][1] = 0;

    while (!q.empty()) {
        point curr = q.front().first;
        int level = q.front().second.first;
        int smell = q.front().second.second;
        q.pop();

        for (int i = 0; i < 4; i++) {
            point next = {curr.x + dx[i], curr.y + dy[i]};

            if (next.x > 0 && next.y > 0 && next.x <= N && next.y <= M && (visited[next.x][next.y] < 0 || visited[next.x][next.y] > level)) {
                if (arr[next.x][next.y] == 0)
                    continue;

                if (arr[next.x][next.y] == 1) {
                    visited[next.x][next.y] = level + 1;
                    q.push({next, {level + 1, smell}});
                }

                if (arr[next.x][next.y] == 2) {
                    visited[next.x][next.y] = level + 1;
                    q.push({next, {level + 1, true}});
                }

                if (arr[next.x][next.y] == 3 && smell) {
                    visited[next.x][next.y] = level + 1;
                    q.push({next, {level + 1, smell}});
                }

                if (arr[next.x][next.y] == 4 && !purple[next.x][next.y][i]) {
                    int tmp = level + 1;
                    // cout << next.x << " " << next.y << endl;
                    while (next.x >= 0 && next.y >= 0 && next.x <= N && next.y <= M && arr[next.x][next.y] == 4 && !purple[next.x][next.y][i]) {
                        purple[next.x][next.y][i] = 1;
                        next.x += dx[i];
                        next.y += dy[i];
                        tmp++;
                    }
                    // cout << next.x << " " << next.y << endl;
                    if (visited[next.x][next.y] == -1)
                        visited[next.x][next.y] = tmp;
                    else
                        visited[next.x][next.y] = min(tmp, visited[next.x][next.y]);
                    if (arr[next.x][next.y] == 2) {
                        q.push({next, {tmp, true}});
                    } else {
                        q.push({next, {tmp, false}});
                    }
                }
            }
        }
    }

    cout << visited[N][M];
}