Submission #401797

#	Time	Username	Problem	Language	Result	Execution time	Memory
401797		jli12345	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	1498 ms	144792 KiB

tracks

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

typedef pair<int, int> pii;
#define f first
#define s second


int N, M;
char arr[4100][4100];

int depth[4100][4100];

struct comp{
	bool operator()(const pair<pii, int> &a, const pair<pii, int> &b){
		return a.s > b.s;
	}
};

int xd[4] = {1, -1, 0, 0};
int yd[4] = {0, 0, 1, -1};

int main(){
	cin >> N >> M;
	for (int i = 1; i <= N; i++){
		for (int j = 1; j <= M; j++){
			cin >> arr[i][j];
		}
	}
	deque<pair<pii, int>> dq;
	dq.push_back({{1, 1}, 1});
	depth[1][1] = 1;
	while (!dq.empty()){
		int x = dq.front().f.f;
		int y = dq.front().f.s;
		int w = dq.front().s;
		dq.pop_front();
		for (int i = 0; i < 4; i++){
			int nx = x+xd[i];
			int ny = y+yd[i];
			if (nx >= 1 && nx <= N && ny >= 1 && ny <= M && arr[nx][ny] != '.' && !depth[nx][ny]){
				if (arr[x][y] == arr[nx][ny]){
					depth[nx][ny] = depth[x][y];
					dq.push_front({{nx, ny}, depth[nx][ny]});
				} else {
					depth[nx][ny] = depth[x][y]+1;
					dq.push_back({{nx, ny}, depth[nx][ny]});
				}
			}
		}
	}
	int ans = 0;
	for (int i = 1; i <= N; i++){
		for (int j = 1; j <= M; j++){
			ans = max(ans, depth[i][j]);
		}
	}
	cout << ans << "\n";
}

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:36:7: warning: unused variable 'w' [-Wunused-variable]
   36 |   int w = dq.front().s;
      |       ^

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