Submission #336751

#	Time	Username	Problem	Language	Result	Execution time	Memory
336751		gozonite	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	1167 ms	143720 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<pair<int, int>> vii;
typedef pair<int, int> pi;
#define MOD 1000000007LL

int H, W;
string grid[4000];
int depth[4000][4000];

int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
bool ins(int x, int y) {
    return x >= 0 && y >= 0 && x < H && y < W && grid[x][y] != '.';
}

int main() {
    cin >> H >> W;
    for (int i = 0; i < H; i++) cin >> grid[i];
    for (int i = 0; i < H; i++)
        for (int j = 0; j < W; j++) depth[i][j] = 1e9;
    depth[0][0] = 1;
    int ans = 1;
    deque<pair<int, int>> q; q.push_front({0, 0});
    while (!q.empty()) {
        int vr = q.front().first, vc = q.front().second; q.pop_front();
        ans = max(ans, depth[vr][vc]);
        for (int i = 0; i < 4; i++) {
            int nr = vr + dx[i], nc = vc + dy[i];
            if (ins(nr, nc) == false) continue;
            int w = grid[vr][vc] != grid[nr][nc];
            if (depth[vr][vc]+w < depth[nr][nc]) {
                depth[nr][nc] = depth[vr][vc]+w;
                if (w == 0) q.push_front({nr, nc});
                else q.push_back({nr, nc});
            }
        }
        //cout << "Finished rep for " << vr << " " << vc << " " << depth[vr][vc] << endl;
    }
    cout << ans << endl;
    
    /*cout << "Debugging depth" << endl;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            cout << depth[i][j] << " ";
        }
        cout << endl;
    }*/
}

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