Submission #1284640

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284640		crunchymon	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	1783 ms	448900 KiB

tracks

#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define all(v) v.begin(),v.end()
#define pb push_back
#define v vector

void solve(){
	int n,m; cin >> n >> m;

	v<v<char>> grid(n , v(m , '.'));
	vector<vector<int>> weights(n , vector <int> (m , 0));
	v<pair<int,int>> edges = {{1,0} , {-1 , 0} , {0 , 1} , {0 , -1}};

	for (int i =0; i<n; i++){
		for (int j = 0; j<m; j++){
			char c; cin >> c;
			grid[i][j] = c;
		}
	}

	deque <v<int>> q;
	q.push_back({0,0});
	int ans = 1;
	weights[0][0] = 1;

	while (q.size()){
		v<int> temp= q.front();
		int i = temp[0];
		int j = temp[1];
		ans = max(ans , weights[i][j]);
		q.pop_front();

		for (auto [x , y] : edges){
			int xx = x + i;
			int yy = y + j;
			if (xx >= 0 && xx <n && yy >=0 && yy<m && grid[xx][yy] != '.' && weights[xx][yy] == 0){
				if (grid[xx][yy] == grid[i][j]){
					q.push_front({xx, yy});
					weights[xx][yy] = weights[i][j];
				}
				else{
					q.push_back({xx,yy});
					weights[xx][yy] = weights[i][j] + 1;
				}

			}
		}

	}

	cout<<ans;


	// for (int i = 0; i<n; i++){
	// 	for (int j = 0; j<m; j++){
	// 		cout<<weights[i][j]<<" ";
	// 	}
	// 	cout<<endl;
	// }
}

int32_t main(){
	// int n; cin >> n;
	int n = 1;
	for (int i = 0; i<n; i++){
		solve();
	}
	return 0;
}

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