Submission #717014

#	Time	Username	Problem	Language	Result	Execution time	Memory
717014		geometry216	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	1418 ms	118984 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
int H, W;

int dx[4]{-1, 1, 0, 0}, dy[4]{0, 0, -1, 1};
char grid[4000][4000];
int lvls[4000][4000];

bool good(int r, int c){
	if(r<0 || r>=H || c<0 || c>=W || lvls[r][c]!=0 || grid[r][c]=='.') return false;
	return true;
}

int main() {
	//# of F connected componetntes + 1 or # of R compoentns + 1
	cin >> H >> W;
	for (int r=0; r<H; r++){
		for (int c=0; c<W; c++){
			cin >> grid[r][c];
		}
	}
	deque<pair<int, int>> dq;
	dq.push_back({0, 0});
	lvls[0][0]=1;
	int ans = 1;
	
	while(!dq.empty()){
		int x, y;
		tie(x, y) = dq.front();
		dq.pop_front();
		ans = max(ans, lvls[x][y]);
		for (int i=0; i<4; i++){
			int xnew = x+dx[i]; int ynew = y+dy[i];
			if(!good(xnew, ynew)) continue;
			if(grid[xnew][ynew]==grid[x][y]){
				lvls[xnew][ynew]=lvls[x][y];
				dq.push_front({xnew, ynew});
			}
			else{
				lvls[xnew][ynew]=1+lvls[x][y];
				dq.push_back({xnew, ynew});
			}
		}
	}

	cout << ans << endl;
}

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