Submission #256286

#	Time	Username	Problem	Language	Result	Execution time	Memory
256286		Saboon	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	694 ms	129028 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const int maxn = 4000 + 10;

int h[maxn][maxn];
string s[maxn];

int adjx[] = {0, -1, 0, 1};
int adjy[] = {1, 0, -1, 0};

int main(){
	ios_base::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> s[i];
	deque<pair<int,int>> deQ;
	memset(h, -1, sizeof h);
	h[0][0] = 1;
	deQ.push_back({0,0});
	int answer = 0;
	while (!deQ.empty()){
		auto it = deQ.front();
		deQ.pop_front();
		int x = it.first, y = it.second;
		answer = max(answer, h[x][y]);
		for (int z = 0; z < 4; z++){
			int nx = x + adjx[z], ny = y + adjy[z];
			if (0 <= nx and nx < n and 0 <= ny and ny < m and s[nx][ny] != '.'){
				int w = (s[nx][ny] != s[x][y]);
				if (h[nx][ny] != -1 and h[nx][ny] <= h[x][y] + 1)
					continue;
				h[nx][ny] = h[x][y] + w;
				if (w == 0)
					deQ.push_front({nx,ny});
				else
					deQ.push_back({nx,ny});
			}
		}
	}
	cout << answer << endl;
}

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