Submission #1035863

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035863		Callie	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	903 ms	136376 KiB

tracks

//Tracks in the Snow
#include <iostream>
#include <vector>
#include <deque>

#define pr pair<int, int>
#define prr pair<pr, int>
#define f first
#define s second
using namespace std;

int dx[4] = {1, -1, 0, 0};
int dy[5] = {0, 0, 1, -1};

int main() {
	int height, width;
	cin >> height >> width;
	vector<vector<int> > map(height, vector<int> (width, 0));
	
	for(int i = 0; i < height; i++) {
		string curr;
		cin >> curr;
		for(int j = 0; j < width; j++) {
			if(curr.substr(j, 1) == ".") map[i][j] = 0;
			else if(curr.substr(j, 1) == "R") map[i][j] = 1;
			else map[i][j] = 2;
			
			//cout << curr << " ";
		}
		//cout << endl;
	}
	
	/*for(int i = 0; i < height; i++) {
		for(int j = 0; j < width; j++) {
			cout << map[i][j] << " ";
		}
		cout << endl;
	}*/
	
	deque<prr> q;
	prr p;
	p.f.f = 0;
	p.f.s = 0;
	p.s = map[0][0];
	q.push_back(p);
	
	int count = 0;
	int track = -1;
	vector<vector<bool> > visited(height, vector<bool>(width, false));
	while(!q.empty()) {
		prr curr = q.front();
		q.pop_front();
		
		int x = curr.f.f;
		int y = curr.f.s;
		int type = curr.s;
		//cout << x << " " << y << " " << type << endl;
		
		if(type != track) {
			count++;
			track = type;
		}
		
		for(int i = 0; i < 4; i++) {
			int nextx = x + dx[i];
			int nexty = y + dy[i];
			
			if(nextx < 0 || nextx >= height) continue;
			if(nexty < 0 || nexty >= width) continue;
			if(visited[nextx][nexty]) continue;
			
			visited[nextx][nexty] = true;
			int nexttype = map[nextx][nexty];
			if(nexttype == 0) continue;
			
			prr n;
			n.f.f = nextx;
			n.f.s = nexty;
			n.s = nexttype;
			if(nexttype == type) {
				q.push_front(n);
			}
			else q.push_back(n);
		}
	}
	
	cout << count << endl;
}

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