제출 #256241

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
256241		amoo_safar	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	604 ms	139016 KiB

tracks

// Zende bad Shoma nasime faghat !
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

const ll Mod = 1000000007LL;
const int N = 4e3 + 10;
const ll Inf = 2242545357980376863LL;
const ll Log = 30;

int n, m, dis[N][N];
str A[N];
pii adj[] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
deque<pii> dq;

inline bool val(int x, int y){
	return (0 <= x) && (x < n) && (0 <= y) && (y < m) && (A[x][y] != '.');
} 
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for(int i = 0; i < n; i++)
		cin >> A[i];

	if(A[0][0] == '.') return cout << "0\n", 0;
	memset(dis, 31, sizeof dis);

	dis[0][0] = 1;
	dq.pb({0, 0});
	
	int x, y, nx, ny;
	int ans = 1;
	while(!dq.empty()){
		x = dq.front().F; y = dq.front().S;
		dq.pop_front();
		//cerr << "# " << x << ' ' << y << '\n';
		for(auto &[X, Y] : adj){
			nx = x + X; ny = y + Y;
			//cerr << nx << ' ' << ny << '\n';
			//if(val(nx, ny)) cerr << nx << ' ' << ny << ' ' << A[nx][ny] << '\n';
			if(val(nx, ny) && dis[nx][ny] > dis[x][y] + (A[x][y] == A[nx][ny] ? 0 : 1)){
				if(A[x][y] == A[nx][ny]){
					dis[nx][ny] = dis[x][y];
					dq.push_front({nx, ny});
				} else {
					dis[nx][ny] = dis[x][y] + 1;
					dq.push_back({nx, ny});
					ans = dis[nx][ny];
				}
			}
		}
	}
	cout << ans << '\n';
	return 0;
}

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