Submission #1267414

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267414		cmiuc	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	967 ms	129544 KiB

tracks

#include <iostream>
#include <deque>

using namespace std;
const int N = 5000;
char a[N][N];
int Min[N][N];
deque<pair<int,int>> vc = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};

int main(){
	int n, m, Mx = 1;
	cin>>n>>m;

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

	for (int i=0;i<=n+1;i++){
		for (int j=0;j<=m+1;j++)
			Min[i][j] = 1e9;
	}

	Min[1][1] = 1;
	deque<pair<int,int>> Q;
	Q.push_back({1, 1});

	while (Q.size() > 0){
		auto [i, j] = Q.front();
		Q.pop_front();

		for (auto [ia, ja] : vc){
			int I = i + ia, J = j + ja;
			int c = (a[i][j] != a[I][J]);
			if (min(I, J) < 1 or I > n or J > m or a[I][J] == '.' or Min[I][J] <= Min[i][j] + c)
				continue;
			Min[I][J] = Min[i][j] + c;
			if (c == 1)
				Q.push_back({I, J});
			else
				Q.push_front({I, J});
			// if (Min[I][J] == 3)
			// 	cout<<I<<" "<<J<<endl;
			Mx = max(Mx, Min[I][J]);
		}
	}
	cout<<Mx<<'\n';

	// for (int i=1;i<=n;i++){
	// 	for (int j=1;j<=m;j++)
	// 		cout<<(a[i][j] == '.' ? 0 : Min[i][j]);
	// 	cout<<'\n';
	// }

}

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