Submission #1261422

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261422		dhuyyyy	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	776 ms	224176 KiB

tracks

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;

using ll = long long;
using ii = pair<int,int>;
using pii = pair<int,ii>;
using aa = array<int,4>;

const int N = 4005;
const int INF = 1e9;
const int MOD = 1e9+7;

int n,m,d[N][N],u,v,ans = 0;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
char a[N][N];
bool ok(int i,int j){
    return i >= 1 && i <= n && j >= 1 && j <= m && a[i][j] != '.';
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++) cin >> a[i][j];
    }
    deque<ii> dq;
    dq.push_front({1,1});
    d[1][1] = 1;
    while (!dq.empty()){
        tie(u,v) = dq.front();
        dq.pop_front();
        for (int k = 0; k < 4; k++){
            int x = u + dx[k];
            int y = v + dy[k];
            if (ok(x,y) && d[x][y] == 0){
                if (a[u][v] == a[x][y]){
                    d[x][y] = d[u][v];
                    dq.push_front({x,y});
                } else{
                    d[x][y] = d[u][v] + 1;
                    dq.push_back({x,y});
                }
            }
        }
    }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            ans = max(ans,d[i][j]);
        }
    }
    cout << ans;
    return 0;
}
/*
⠀⠀⠀⠀⠀⠀⢀⡤⣤⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⡀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⢀⡏⠀⠀⠈⠳⣄⠀⠀⠀⠀⠀⣀⠴⠋⠉⠉⡆⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀⠀⠈⠉⠉⠙⠓⠚⠁⠀⠀⠀⠀⣿⠀⠀⠀⠀⠀
⠀⠀⠀⠀⢀⠞⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠹⣄⠀⠀⠀⠀
⠀⠀⠀⠀⡞⠀⠀⠀⠀⠀⠶⠀⠀⠀⠀⠀⠀⠦⠀⠀⠀⠀⠀⠸⡆⠀⠀⠀
⢠⣤⣶⣾⣧⣤⣤⣀⡀⠀⠀⠀⠀⠈⠀⠀⠀⢀⡤⠴⠶⠤⢤⡀⣧⣀⣀⠀
⠻⠶⣾⠁⠀⠀⠀⠀⠙⣆⠀⠀⠀⠀⠀⠀⣰⠋⠀⠀⠀⠀⠀⢹⣿⣭⣽⠇
⠀⠀⠙⠤⠴⢤⡤⠤⠤⠋⠉⠉⠉⠉⠉⠉⠉⠳⠖⠦⠤⠶⠦⠞⠁⠀⠀⠀
*/

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