제출 #649074

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
649074		rickbaishuak	Tracks in the Snow (BOI13_tracks)	C++14	97.81 / 100	787 ms	186124 KiB

tracks

#include <bits/stdc++.h>
#define pb push_back
#define er erase
#define in insert
#define s(a, x, y) sort(a.begin()+x, a.begin()+y);
#define r(a, x, y) reverse(a.begin()+x, a.begin()+y);
#define mp make_pair
#define F first
#define S second
#define ll long long
#define ld long double
#define forn(i, a, b) for(int i=a; i<=b; i++)
#define form(i, a, b) for(int i=a; i>=b; i--)
#define PI 3.14159265358979
#define inf 2147483647
#define sp setprecision
#define pii pair <int, int>
#define gcd __gcd
#define endl '\n'
#define sz(a) (int)a.size()
using namespace std;
const ll N = 4000 + 13;
ll t1, n, m, d[N][N], ans, x, y;
ll dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
string t;
char s[N][N];
deque <pii> q;
bool st1[N][N], st2[N][N];
pii v;
void solve(){
	cin >> n >> m;
	forn (i, 1, max (n, m)){
		s[i][0] = s[0][i] = s[n + 1][i] = s[i][m + 1] = '.';
	}
	forn (i, 1, n){
		cin >> t;
		forn (j, 1, m){
			s[i][j] = t[j - 1];
		}
	}
	q.push_back ({1, 1});
	d[1][1] = 1;
	while (sz(q)){
//		for (pii p: q) cout << p.F << " " << p.S << "  ";
//		cout << endl;
		v = q[0];
		q.pop_front();
		forn (i, 0, 3){
			x = v.F + dx[i];
			y = v.S + dy[i];
			if (s[x][y] != '.' && !d[x][y]){
				if (s[x][y] == s[v.F][v.S]){
					d[x][y] = d[v.F][v.S];
					q.push_front ({x, y});
				}
				else{
					d[x][y] = d[v.F][v.S] + 1;
					q.push_back ({x, y});
					ans = max (ans, d[x][y]);
				}
			}
		}
	}
//	forn (i, 1, n){
//		forn (j, 1, m){
//			cout << d[i][j];
//		}
//		cout << endl;
//	}
	cout << ans << endl;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
//	cin >> t1;
	t1 = 1;
	while (t1 --){
		solve();
	}
	return 0;
}
/*
5
0.50 0.29 0.49 0.95 0.66
2 3
0 3
3 4
2 1

5
0.50 0.29 0.49 0.95 0.83
2 3
0 3
3 4
2 1
1
4 0.66
*/

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