Submission #971865

#	Time	Username	Problem	Language	Result	Execution time	Memory
971865		pete555	Tracks in the Snow (BOI13_tracks)	C++17	0 / 100	847 ms	277268 KiB

tracks

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

#define pi pair<int,int>
#define ll long long
#define pb push_back
#define pf push_front

const int MOD = 1e9+7;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};

int main()
{
	cin.tie(0)->sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	string s[n];
	for(int i=0; i<n; i++)
		cin >> s[i];
	deque<pi> q;
	vector<vector<int>> d(n, vector<int>(m));
	vector<vector<bool>> vis(n, vector<bool>(m));
	d[0][0] = 0;
	q.pb({0, 0});
	while(q.size()){
		pi u = q.front();
		q.pop_front();
		if(vis[u.first][u.second]) continue;
		vis[u.first][u.second] = true;
		for(int i=0; i<4; i++){
			int new_x = u.first + dx[i];
			int new_y = u.second + dy[i];
			if(new_x < 0 or new_x >= n or new_y < 0 or new_y >= m) continue;
			if(s[new_x][new_y] == s[u.first][u.second]){
				d[new_x][new_y] = d[u.first][u.second];
				q.pf({new_x, new_y});
			}else if(s[new_x][new_y] != '.'){
				d[new_x][new_y] = d[u.first][u.second] + 1;
				q.pb({new_x, new_y});
			}
		}
	}
	cout << d[n-1][m-1] << '\n';
}

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