제출 #753169

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
753169		MISM06	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	729 ms	108692 KiB

tracks

//0 1 1 0 1
//0 1 0 0 1
//1 0 0 1 1
//0 1 1 0 1
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("avx2")

using namespace std;

#define F 			first
#define S 			second
#define pb 			push_back
#define sze			size()
#define	all(x)		x.begin() , x.end()
#define wall__		cout << "--------------------------------------\n";
#define kids		int mid = (tl + tr) >> 1, cl = v << 1, cr = v << 1 | 1
#define file_io		freopen("input.cpp", "r", stdin); freopen("output.cpp", "w", stdout);

typedef long long ll;
typedef long double dl;
typedef pair < short int , short int > pii;
typedef pair < int , ll > pil;
typedef pair < ll , int > pli;
typedef pair < ll , ll > pll;
typedef pair < int , pii > piii;
typedef pair < ll, pll > plll;


const ll N = 4000 + 3;
const ll M = N * N;
const ll mod = 1e9 + 7;
const ll inf = 2e16;
const ll rinf = -2e16;
const ll INF = 1e9 + 10;
const ll rINF = -1e9 - 10;
const ll lg = 32;

int n, m, h[N][N], ans;
char c[N][N];

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	cin >> n >> m;
	for (int i = 1; i <= n; i++) c[i][0] = '.';
	for (int i = 1; i <= m; i++) c[0][i] = '.';
	for (int i = 1; i <= n; i++) 
		for (int j = 1; j <= m; j++) {
			cin >> c[i][j];
			h[i][j] = INF;
		}
	deque < pii > q; q.pb({1, 1}); h[1][1] = 0;
	while (q.sze) {
		pii v = q.back();
		q.pop_back();
		short int x = v.F, y = v.S; ans = max(h[x][y], ans);
		for (short int i = -1; i <= 1; i++) {
			if (c[x + i][y] == c[x][y]) {
				if (h[x][y] < h[x + i][y]) {
					h[x + i][y] = h[x][y];
					q.push_back({x + i, y});
				}
			} else if (c[x + i][y] != '.') {
				if (h[x][y] + 1 < h[x + i][y]) {
					h[x + i][y] = h[x][y] + 1;
					q.push_front({x + i, y});
				}
			}
			if (c[x][y + i] == c[x][y]) {
				if (h[x][y] < h[x][y + i]) {
					h[x][y + i] = h[x][y];
					q.push_back({x, y + i});
				}
			} else if (c[x][y + i] != '.') {
				if (h[x][y] + 1 < h[x][y + i]) {
					h[x][y + i] = h[x][y] + 1;
					q.push_front({x, y + i});
				}
			}
		}
	}
	cout << ++ans << '\n';
    return 0;
}
/*
5 12
RRRRRRRR....
F...F..RRRRR
R...F..FR..R
RR..FF.FFFFR
FRRRRFFFFFRR
*/
//shrek will AC this;

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