Submission #716984

#	Time	Username	Problem	Language	Result	Execution time	Memory
716984		study	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	469 ms	101684 KiB

tracks

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

const int N = 4000;

string grid[N];
bool vu[N][N];
int h,w;

vector<pair<int,int>> dir = {{1,0},{0,1},{-1,0},{0,-1}};

struct node{
	int x,y,val;
};

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> h >> w;
	for (int i=0; i<h; ++i){
		cin >> grid[i];
	}
	if (grid[0][0] == '.'){
		cout << 0;
		return 0;
	}
	deque<node> q;
	q.emplace_back(node{0,0,1});
	int ans = 0;
	while (!q.empty()){
		auto f = q.front();
		q.pop_front();
		ans = max(ans,f.val);
		for (auto i:dir){
			int nx = i.first+f.x, ny = i.second+f.y;
			if (nx >= 0 and ny >= 0 and nx < h and ny < w and !vu[nx][ny] and grid[nx][ny] != '.'){
				vu[nx][ny] = true;
				if (grid[f.x][f.y] != grid[nx][ny]) q.emplace_back(node{nx,ny,f.val+1});
				else q.emplace_front(node{nx,ny,f.val});
			}
		}
	}
	cout << ans;
	return 0;
}

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