Submission #1124056

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124056		Tozzyyyy	Tracks in the Snow (BOI13_tracks)	C++20	0 / 100	823 ms	224584 KiB

tracks

#pragma GCC optimize("Ofast" , "unroll-loops")
#include<bits/stdc++.h>

#define bit(i , j) ((j >> i) & 1)
#define fi first
#define se second
#define all(x) (x).begin() , (x).end()
using namespace std;

#define int long long
#define pll pair<int , int>

const int MAXN = 4040;
char a[MAXN][MAXN];
int d[MAXN][MAXN];
int dx[4] = {-1 , 0 , 1 , 0};
int dy[4] = {0 , -1 , 0 , 1};
const int inf = 1e9+1;
int32_t main(){
	//freopen("A.inp", "r", stdin);
	//freopen("robot.out", "w", stdout);
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n , m; cin >> n >> m;
	for(int i = 1 ; i <= n ; i++){
		for(int j = 1 ; j <= m ; j++) cin >> a[i][j];
	}

	deque<pll> Q;
	for(int i = 1 ; i <= n ; i++){
		for(int j = 1;  j <= m ; j++) d[i][j] = -1;
	}
	auto out = [&](int x , int y){
		return (x < 1 || x > n || y < 1 || y > m);
	};

	Q.push_back({1 , 1});
	d[1][1] = 0;

	while(Q.size()){
		pll t = Q.front();
		Q.pop_front();
		for(int i = 0 ; i < 4 ; i++){
			int x = t.fi + dx[i] , y = t.se + dy[i];
			if(out(x , y)) continue;
			if(d[x][y] == -1 && a[x][y] != '.'){
				if(a[x][y] == a[t.fi][t.se]) d[x][y] = d[t.fi][t.se] , Q.push_front({x , y});
				else d[x][y] = d[t.fi][t.se] + 1, Q.push_back({x , y});
			}
		}
	}

	int ans = 0;
	for(int i = 1 ; i <= n ; i++) for(int j = 1 ; j <= m ; j++) ans = max(ans , d[i][j]);
	cout << ans << "\n";

	return 0;
}

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