Submission #1247696

#TimeUsernameProblemLanguageResultExecution timeMemory
1247696veternositTracks in the Snow (BOI13_tracks)C++20
100 / 100
1057 ms85548 KiB
#include <bits/stdc++.h>
using namespace std;

#define BOTH 3
#define FOX 2
#define RAB 1
#define NONE 0

int main() {
    int N, M;
    cin >> N >> M;
    vector<vector<int>> map(N, vector<int>(M, 0));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            char c;
            cin >> c;

            map[i][j] = c == 'F' ? FOX : (c == 'R' ? RAB : NONE);
        }
    }

    queue<pair<int,int>> q;
    q.push({0, 0});

    queue<pair<int,int>> newQ;

    vector<vector<bool>> vis(N, vector<bool>(M, false));
    vis[0][0] = true;

    vector<int> xs = {0, 1, 0, -1};
    vector<int> ys = {1, 0, -1, 0};
    bool cont = true;
    int l = 0;
    while (!q.empty()) {
        while (!q.empty()) {
            pair<int,int> v = q.front();
            q.pop();
            for (int dir = 0; dir < 4; dir++) {
                int x = v.first + xs[dir];
                int y = v.second + ys[dir];
                if (x < 0 || x >= N || y < 0 || y >= M) continue;
                if (vis[x][y]) continue;
                if (map[x][y] == NONE) continue;
                if (map[x][y] == map[v.first][v.second]) {
                    q.push({x, y});
                    vis[x][y] = true;
                } else {
                    newQ.push({x, y});
                    vis[x][y] = true;
                }
            }
        }
        q = newQ;
        queue<pair<int, int>> empty;
        newQ = empty;
        l++;
    }

    cout << (map[0][0] != NONE ? l : 0);
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...