Submission #1079403

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079403		mizunokaze	Tracks in the Snow (BOI13_tracks)	C++17	2.19 / 100	274 ms	214540 KiB

tracks

#include <bits/stdc++.h>
#define int long long
#define chiikawa ios_base::sync_with_stdio(0); cin.tie(0);
#define ff first
#define ss second
#define sz(x) (x).size()
#define pii pair<int,int>
#define plii pair<int, pair<int,int>>
#define lc u<<1
#define rc u<<1|1
#define rep(i,x,y) for(int i=x;i<=y;++i) 
#define per(i,x,y) for(int i=x;i>=y;--i)
#define INF 0x3f3f3f3f
#define lowbit(x) (x & (-x))
using namespace std;
int n, m, dep[4005][4005], ans = 1;
int dr[4] = {1, -1, 0, 0}, dc[4] = {0, 0, 1, -1};
string sn[4005];

bool check(int x, int y){
	return (x >= 0 && x < n && y >= 0 && y < m && sn[x][y] == '.');
}

signed main(){
	chiikawa
	cin >> n >> m;

	for(int i = 0 ;i < n; i ++) cin >> sn[i];

	deque<pii> q;
	q.push_back({0, 0});
	dep[0][0] = 1;

	while(sz(q)){
		auto c = q.front();
		int u = c.ff, v = c.ss;
		q.pop_front();

		ans = max(ans, dep[u][v]);

		for(int k = 0; k < 4; k ++){
			int i = u + dr[k], j = v + dc[k];

			if(check(i, j) && dep[i][j] == 0){
				if(sn[i][j] == sn[u][v])
					dep[i][j] = dep[u][v], q.push_front({i, j});
				else
					dep[i][j] = dep[u][v] + 1, q.push_back({i, j});
			}
		}
	} 	
	cout << ans << endl;
}

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