제출 #1317553

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1317553		nxk02102010	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	666 ms	208980 KiB

tracks

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n,m;cin >> n >> m;
	vector<vector<char>> a(n + 1,vector<char> (m + 1));
	for(int i = 1;i <= n;i++) for(int j =  1;j <= m;j++) cin >> a[i][j];
	auto inside = [&](int i,int j) -> bool{
		return i >= 1 && j >= 1 && i <= n && j <= m && a[i][j] != '.';
	};
	vector<vector<int>> d(n + 1,vector<int> (m + 1));
	deque<pair<int,int>> q;
	q.push_front({1,1});
	d[1][1] = 1;
	const int dx[] = {1,-1,0,0};
	const int dy[] = {0,0,-1,1};
	int ans = 0;
	while(!q.empty()){
		auto top = q.front();
		q.pop_front();
		int i = top.F;
		int j = top.S;
		ans = max(ans,d[i][j]);
		for(int t =0 ;t < 4;t++){
			int x = i + dx[t];
			int y = j + dy[t];
			if(inside(x,y) && d[x][y] == 0){
				if(a[x][y] == a[i][j]){
					d[x][y] = d[i][j];
					q.push_front({x,y});
				}
				else{
					d[x][y] = d[i][j] + 1;
					q.push_back({x,y});
				}
			}
		}
	}
	cout << ans << '\n';
}

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