Submission #368077

#	Time	Username	Problem	Language	Result	Execution time	Memory
368077		R3KT	Tracks in the Snow (BOI13_tracks)	C++17	6.67 / 100	2109 ms	343312 KiB

tracks

#include <iostream>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <string>
#include <string.h>
#include <array>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
using namespace std;
typedef long long ll;

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

int dfs() {
    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 (visited[x][y] != 0 && visited[x][y] <= count) continue;
        if (arr[x][y] != type) {
            count++;
        }
        visited[x][y] = count;
        ans = max(ans, count);
        // cout << count << " " << type << " " << x << " " << y << " " << ans << "\n";
        pq.push({count, {arr[x][y], {x+1, y}}});
        pq.push({count, {arr[x][y], {x-1, y}}});
        pq.push({count, {arr[x][y], {x, y+1}}});
        pq.push({count, {arr[x][y], {x, y-1}}});
    }
    return ans;
}

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

    int ans = dfs();

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

    cout << ans;
}

• Subtask 1: 6.666666666666667 / 30
• Subtask 2: 0 / 70