Submission #810770

#	Time	Username	Problem	Language	Result	Execution time	Memory
810770		serifefedartar	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	570 ms	124912 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define MOD 1000000007
#define LOGN 20
#define MAXN 1000005
 
const int delRow[] = {-1, 0, 0, 1};
const int delCol[] = {0, -1, 1, 0};
int H, W;
vector<string> grid;
int main() {
    fast
    cin >> H >> W;
 
    grid = vector<string>(H);
    for (int i = 0; i < H; i++)
        cin >> grid[i];
    
    vector<vector<int>> depth(H, vector<int>(W, 0));    
    deque<pair<int,int>> dq;
    dq.push_back({0, 0});
    depth[0][0] = 1;
    int ans = 0;
    while (dq.size()) {
        int row = dq.front().f;
        int col = dq.front().s;
        ans = max(ans, depth[row][col]);
        dq.pop_front();

        for (int i = 0; i < 4; i++) {
            int nRow = row + delRow[i];
            int nCol = col + delCol[i];
            if (nRow >= 0 && nRow < H && nCol >= 0 && nCol < W && grid[nRow][nCol] != '.' && depth[nRow][nCol] == 0) {
                if (grid[row][col] == grid[nRow][nCol]) {
                    depth[nRow][nCol] = depth[row][col];
                    dq.push_front({nRow, nCol});
                } else {
                    depth[nRow][nCol] = depth[row][col] + 1;
                    dq.push_back({nRow, nCol});
                }
            }
        }
    }
    cout << ans << "\n";
}

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