Submission #340530

#	Time	Username	Problem	Language	Result	Execution time	Memory
340530		rqi	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	1715 ms	151552 KiB

tracks

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pi;

#define mp make_pair
#define f first
#define s second

#define sz(x) (int)(x).size()

int xd[4] = {1, 0, -1, 0};
int yd[4] = {0, 1, 0, -1};

const int MOD = 1e9+7;

int grid[4005][4005];
int dist[4005][4005];

int ans = 1;

int main(){
	int H, W;
	cin >> H >> W;
	for(int i = 1; i <= H; i++){
		string s;
		cin >> s;
		for(int j = 0; j < W; j++){
			if(s[j] == 'R'){
				grid[i][j+1] = 1;
			}
			else if(s[j] == 'F'){
				grid[i][j+1] = 2;
			}
		}
	}

	for(int i = 1; i <= H; i++){
		for(int j = 1; j <= W; j++){
			dist[i][j] = MOD;
		}
	}

	
	queue<pi> q; //have ans value
	queue<pi> nq;

	dist[1][1] = 1;
	q.push(mp(1, 1));

	while(sz(q)){
		pi co = q.front();
		q.pop();

		//cout << co.f << " " << co.s << "\n";

		for(int d = 0; d < 4; d++){
			int x = co.f+xd[d];
			int y = co.s+yd[d];

			

			if(grid[x][y] == 0) continue;

			if(dist[x][y] != MOD) continue;

			//cout << "x y: " << x << " " << y << "\n";

			if(grid[x][y] == grid[co.f][co.s]){
				dist[x][y] = ans;
				q.push(mp(x, y));
			}
			else{
				dist[x][y] = ans+1;
				nq.push(mp(x, y));
			}
		}

		if(sz(q) == 0){
			if(sz(nq) == 0) break;
			swap(nq, q);
			//cout << "AD" << "\n";
			ans++;
		}
	}


	cout << ans << "\n";

}

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