Submission #619984

#	Time	Username	Problem	Language	Result	Execution time	Memory
619984		abcisosm5	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	494 ms	130832 KiB

tracks

#include <bits/stdc++.h>
using namespace std;

const int MN = 4000;
string grid[MN] = {};
int dist[MN][MN] = {{}};
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int main(){
	cin.tie(0)->sync_with_stdio(0);

	int H, W; cin >> H >> W;

	for(int i = 0; i < H; i++){
		cin >> grid[i];
	}

	int maxDist = 1;
	dist[0][0] = 1;
	deque<pair<int,int>> d; d.push_front({0,0});

	while(!d.empty()){
		pair<int,int> p = d.front(); d.pop_front();
		int x = p.first; int y = p.second;

		for(int i = 0; i < 4; i++){
			int x_ = x+dx[i]; int y_ = y+dy[i];
			if(x_ < 0 || x_ >= H || y_ < 0 || y_ >= W) continue;
			if(grid[x_][y_] == '.' || dist[x_][y_] > 0) continue;
			
			if(grid[x_][y_] == grid[x][y]){
				dist[x_][y_] = dist[x][y];
				d.push_front({x_,y_});
			} else{
				dist[x_][y_] = dist[x][y]+1;
				maxDist = max(maxDist, dist[x_][y_]);
				d.push_back({x_,y_});
			}
		}
	}

	cout << maxDist;
}

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