Submission #868006

#	Time	Username	Problem	Language	Result	Execution time	Memory
868006		theghostking	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	1403 ms	333384 KiB

tracks

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

#define int long long

int h,w;

int hsh(int i, int j){
    // 0 <= i < h
    // 0 <= j < w
    return (i*w)+j;
}

pair<int,int> unhsh(int x){
    return {x/w,x%w};
}

signed main() {
    cin >> h >> w;
    int grid[h][w];
    bool visited[h][w];
    for (int i = 0; i<h; i++){
        for (int j = 0; j<w; j++){
            char a;
            cin >> a;
            if (a == '.') grid[i][j] = 0;
            if (a == 'R') grid[i][j] = 1;
            if (a == 'F') grid[i][j] = 2;
            visited[i][j] = false;
        }
    }

    vector<int> dx = {0,1,0,-1};
    vector<int> dy = {1,0,-1,0};

    int mxn = hsh(h-1,w-1);
    vector<int> dist(mxn+1, 1e9);
    deque<pair<int,int>> q;
    q.push_front({0,0});
    dist[0] = 1;
    int ans = 0;
    while (!q.empty()){
        pair<int,int> v = q.front();
        int vhsh = hsh(v.first,v.second);
        q.pop_front();
        ans = max(ans,dist[vhsh]);
        if (visited[v.first][v.second]) continue;
        visited[v.first][v.second] = true;
        int r = v.first;
        int c = v.second;
        for (int k = 0; k<4; k++){
            int rr = r + dx[k];
            int cc = c + dy[k];
            if (rr < 0 || rr >= h || cc < 0 || cc >= w) continue;
            if (visited[rr][cc]) continue;
            if (grid[rr][cc] == 0) continue;
            int khsh = hsh(rr,cc);
            if (dist[vhsh] + (grid[r][c] != grid[rr][cc]) < dist[khsh]){
                dist[khsh] = dist[vhsh] + (grid[r][c] != grid[rr][cc]);
                if (grid[rr][cc] != grid[r][c]){
                    q.push_back({rr,cc});
                }
                else{
                    q.push_front({rr,cc});
                }
            }
        }
    }
    cout << ans;
    return 0;
}

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