제출 #1130752

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

tracks

#include "bits/stdc++.h"

using namespace std;

#define ln "\n"
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define int long long
const int MOD = 1e9 + 7;
const int inf = 2e18;
const int N = 4005;
int n, m, a[N][N], dist[N][N];
bool block[N][N];
pair<int, int> d[5] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

signed main() {
	cin.tie(0) -> sync_with_stdio(0);
	cin >> n >> m;
	deque<pair<int, int>> q;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			char c; cin >> c;
			if(c == '.') block[i][j] = 1;
			else if(c == 'R') a[i][j] = 1;
			else a[i][j] = 2;
		}
	}
	dist[1][1] = 1;
	int ans = 0;
	q.push_front({1, 1});
	while(sz(q)) {
		auto u = q.front(); q.pop_front();
		int x = u.fi, y = u.se;
		block[x][y] = 1;
		ans = max(ans, dist[x][y]);
		for(int i = 0; i < 4; i++) {
			int nx = x + d[i].fi, ny = y + d[i].se;
			if(nx < 1 or ny < 1 or nx > n or ny > m or block[nx][ny]) continue;
			if(a[nx][ny] == a[x][y]) {
				dist[nx][ny] = dist[x][y];
				q.push_front({nx, ny});
			} else {
				dist[nx][ny] = dist[x][y] + 1;
				q.push_back({nx, ny});
			}
		}
	}
	cout << ans << ln;
    cerr << "\nTime: " << clock() * 1000 / CLOCKS_PER_SEC;
}

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