Submission #1039525

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039525		BaroDP	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	849 ms	132192 KiB

tracks

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

#define pb push_back
#define fi first
#define se second
#define sz(x) int(x.size())
#define fast ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define loop(i, j, n, k) for(int i = j; i <= n; i += k)
#define reloop(i, j, n, k) for (int i = j; i >= n; i +=k)

using ll = long long;
using vi = vector<int>;
using vll = vector<long long>;
using pii = pair<int,int>;
using pss = pair<string,string>;

const int N = 4e3;
char a[N + 5][N + 5];
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
int n, m, depth[N + 5][N + 5];
int ans = 1;
deque<pii>q;
bool inside (int x, int y){
    if (x < 1 || x > n || y < 1 || y > m || a[x][y] == '.')
        return false;
    return true;
}
int main(){
    cin >> n >> m;
    loop(r, 1, n, 1)
        loop(c, 1, m, 1)
            cin >> a[r][c];

    q.push_front({1, 1});
    depth[1][1] = 1;
    while(!q.empty()){
        pii top = q.front(); q.pop_front();
        int x = top.fi, y = top.se;
        ans = max(ans, depth[x][y]);

        loop(k, 0, 3, 1){
            int nx = x + dx[k], ny = y + dy[k];
            if (inside(nx, ny) && depth[nx][ny] == 0){
                if (a[nx][ny] == a[x][y]){
                    depth[nx][ny] = depth[x][y];
                    q.push_front({nx, ny});
                }else{
                    depth[nx][ny] = depth[x][y] + 1;
                    q.push_back({nx, ny});
                }
            }
        }
    }
    cout << ans;
}

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