제출 #1247672

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1247672		veternosit	Tracks in the Snow (BOI13_tracks)	C++20	7.71 / 100	2134 ms	1114112 KiB

tracks

#include <bits/stdc++.h>
using namespace std;

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

bool ff(vector<vector<int>> &map, int type, int N, int M) {
    bool cont = false;
    vector<vector<bool>> vis(N, vector<bool>(M, false)); vis[0][0] = true;
    queue<vector<int>> q;
    q.push({0, 0});
    while (!q.empty()) {
        vector<int> p = q.front(); q.pop();
        vis[p[0]][p[1]] = true;
        if (map[p[0]][p[1]] != BOTH) cont = true;
        map[p[0]][p[1]] = BOTH;
        if (p[0] > 0 && !vis[p[0]-1][p[1]] && (type & map[p[0]-1][p[1]])) q.push({p[0] - 1, p[1]});
        if (p[1] > 0 && !vis[p[0]][p[1]-1] && (type & map[p[0]][p[1]-1])) q.push({p[0], p[1] - 1});
        if (p[0] < N-1 && !vis[p[0]+1][p[1]] && (type & map[p[0]+1][p[1]])) q.push({p[0] + 1, p[1]});
        if (p[1] < M-1 && !vis[p[0]][p[1]+1] && (type & map[p[0]][p[1]+1])) q.push({p[0], p[1] + 1});
    }
    return cont;
}

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);
        }
    }

    if (!map[0][0]) {cout << 0; return 0;}
    
    bool cont = true;
    int type = map[0][0] == FOX ? FOX : RAB;
    int a = 0;
    while (cont) {
        cont = ff(map, type, N, M);
        type ^= 3; // switches
        if (cont) a++;
    }
    cout << a;
}

• Subtask 1: 3.3333 / 30
• Subtask 2: 4.375 / 70