Submission #1247695

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247695		veternosit	Tracks in the Snow (BOI13_tracks)	C++20	19.79 / 100	1099 ms	140568 KiB

tracks

#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] == 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);
}

• Subtask 1: 6.6667 / 30
• Subtask 2: 13.125 / 70