Submission #367970

#	Time	Username	Problem	Language	Result	Execution time	Memory
367970		R3KT	Tracks in the Snow (BOI13_tracks)	C++17	6.67 / 100	2104 ms	134060 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<pair<int, 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.first; int type = cur.first.second; int x = cur.second.first; int y = cur.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) {
            pq.push({{count+1,arr[x][y]},{x,y}});
            continue;
        }
        visited[x][y] = count;
        ans = max(ans, count);
        // cout << count << " " << type << " " << x << " " << y << " " << ans << "\n";
        pq.push({{count, type}, {x+1, y}});
        pq.push({{count, type}, {x-1, y}});
        pq.push({{count, type}, {x, y+1}});
        pq.push({{count, type}, {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