제출 #368083

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
368083		R3KT	Tracks in the Snow (BOI13_tracks)	C++17	80.31 / 100	2096 ms	125548 KiB

tracks

#include <iostream>
#include <vector>
#include <queue>
#include <array>
using namespace std;
typedef long long ll;

const int MaxN = 4e3;
int h, w;
int arr[MaxN][MaxN], visited[MaxN][MaxN];

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

    cin >> h >> w;
    for (int i=0; i<h; i++) {
        for (int j=0; j<w; j++) {
            char cur;
            cin >> cur;
            if (cur == 'F') arr[i][j] = 0;
            else if (cur == 'R') arr[i][j] = 1;
            else arr[i][j] = -1;
        }
    }

    // for (int i=0; i<h; i++) {
    //     for (int j=0; j<w; j++) {
    //         cout << visited[i][j] << " ";
    //     }
    //     cout << "\n";
    // }

    using T = pair<int, pair<int, pair<int, int>>>;
                    // count, type (0 = fox), x, y
    priority_queue<T, vector<T>, greater<T>> pq;
    pq.push({1,{arr[0][0],{0,0}}});
    int ans=0;
    while (!pq.empty()) {
        T cur = pq.top();
        pq.pop();
        int count = cur.first; int type = cur.second.first; int x = cur.second.second.first; int y = cur.second.second.second;
        // if (x < 0 || y < 0 || x >= h || y >= w) continue;
        // if (arr[x][y] == -1) continue;
        if (arr[x][y] != type) {
            count++;
        }
        if (visited[x][y] != 0 && visited[x][y] <= count) continue;
        visited[x][y] = count;
        ans = max(ans, count);
        // cout << count << " " << type << " " << x << " " << y << " " << ans << "\n";
        if (x+1 >= 0 && y >= 0 && x+1 < h && y < w && arr[x+1][y] != -1) {
            pq.push({count, {arr[x][y], {x+1, y}}});
        }
        if (x-1 >= 0 && y >= 0 && x-1 < h && y < w && arr[x-1][y] != -1) {
            pq.push({count, {arr[x][y], {x-1, y}}});
        }
        if (x >= 0 && y+1 >= 0 && x < h && y+1 < w && arr[x][y+1] != -1) {
            pq.push({count, {arr[x][y], {x, y+1}}});
        }
        if (x >= 0 && y-1 >= 0 && x < h && y-1 < w && arr[x][y-1] != -1) {
            pq.push({count, {arr[x][y], {x, y-1}}});
        }
    }

    cout << ans;
}

• Subtask 1: 30 / 30
• Subtask 2: 50.3125 / 70