Submission #646832

#	Time	Username	Problem	Language	Result	Execution time	Memory
646832		beaconmc	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	1200 ms	257288 KiB

tracks

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;

#define FOR(i, x, y) for(ll i=x; i<y; i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)

bool visited[4001][4001];
char grid[4001][4001];
ll depth[4001][4001];

vector<ll> xx = {-1,1,0,0}, yy = {0,0,-1,1};

int main(){
	FOR(i,0,4001){
		FOR(j,0,4001){
			visited[i][j] = 0;
			grid[i][j] = 0;
			depth[i][j] = 0;
		}
	}
	ll n,m;
	cin >> n >> m;
	FOR(i,0,n){
		string temp;
		cin >> temp;
		FOR(j,0,m){
			grid[i][j] = temp[j];
		}
	}
	vector<char> ani;

	if (grid[0][0] == 'F'){
		ani = {'F','R'};
	}else ani = {'R','F'};

	deque<pair<ll,ll>> q;
	q.push_front(make_pair(0,0));

	while (q.size()){
		pair<ll,ll> node = q.front();
		q.pop_front();

		FOR(i,0,4){
			ll x = node.first + xx[i];
			ll y = node.second + yy[i];

			if (0<=x && x<n && 0<=y && y<m && grid[x][y] != '.'){
				if (grid[x][y] == ani[depth[node.first][node.second]%2] && !visited[x][y]){
					visited[x][y] = 1;
					depth[x][y] = depth[node.first][node.second];
					q.push_front(make_pair(x,y));
				}

				if (grid[x][y] != ani[depth[node.first][node.second]%2] && !visited[x][y]){
					depth[x][y] = depth[node.first][node.second]+1;
					visited[x][y] = 1;
					q.push_back(make_pair(x,y));
				}
			}
		}
	}
	ll maxi = -1;

	FOR(i,0,4001){
		FOR(j,0,4001){
			maxi = max(maxi, depth[i][j]);
		}
	}
	cout << maxi+1;
}

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