Submission #113657

#	Time	Username	Problem	Language	Result	Execution time	Memory
113657		sahil_k	Robots (APIO13_robots)	C++14	10 / 100	3 ms	384 KiB

robots

#include <iostream>
#include <set>
#include <limits.h>
using namespace std;
int main () {
	int n, w, h;
	cin >> n >> w >> h;
	char grid[h+2][w+2];
	for (int i=0; i<w+2; i++) {
		grid[0][i] = 'x';
	}
	for (int i=1; i<=h; i++) {
		grid[i][0] = 'x';
		grid[i][w+1] = 'x';
	}
	for (int i=0; i<w+2; i++) {
		grid[h+1][i] = 'x';
	}
	pair<int, int> start;
	pair<int, int> end;
	for (int i=0; i<h; i++) {
		for (int j=0; j<w; j++) {
			cin >> grid[i+1][j+1];
			if (grid[i+1][j+1] == '1') {
				start.first = i+1;
				start.second = j+1;
			} else if (grid[i+1][j+1] == '2') {
				end.first = i+1;
				end.second = j+1;
			}
		}
	}
	set< pair<int, int> > vis;
	set< pair< pair<int, int>, int > > vis1;
	set< pair<int, int> > bound;
	set< pair<int, int> > nbound;
	bound.insert(start);
	int c = 0;
	while (true) {
		for (auto p: bound) {
			vis.insert(p);
			vis1.insert(make_pair(p, c));
		}
		for (auto p: bound) {
			for (int i=p.first-1; i>=0; i--) {
				if (grid[i][p.second] == 'x') {
					if (vis.find(make_pair(i+1, p.second)) == vis.end()) {
						nbound.insert(make_pair(i+1, p.second));
					}
					break;
				}
			}
			for (int i=p.first+1; i<h+2; i++) {
				if (grid[i][p.second] == 'x') {
					if (vis.find(make_pair(i-1, p.second)) == vis.end()) {
						nbound.insert(make_pair(i-1, p.second));
					}
					break;
				}
			}
			for (int i=p.second-1; i>=0; i--) {
				if (grid[p.first][i] == 'x') {
					if (vis.find(make_pair(p.first, i+1)) == vis.end()) {
						nbound.insert(make_pair(p.first, i+1));
					}
					break;
				}
			}
			for (int i=p.second+1; i<w+2; i++) {
				if (grid[p.first][i] == 'x') {
					if (vis.find(make_pair(p.first, i-1)) == vis.end()) {
						nbound.insert(make_pair(p.first, i-1));
					}
					break;
				}
			}
		}
		if (nbound.size() == 0) {
			break;
		}
		bound = nbound;
		nbound.clear();
		c++;
	}
	vis.clear();
	set< pair< pair<int, int>, int > > vis2;
	bound.clear();
	nbound.clear();
	bound.insert(end);
	c = 0;
	while (true) {
		for (auto p: bound) {
			vis.insert(p);
			vis2.insert(make_pair(p, c));
		}
		for (auto p: bound) {
			for (int i=p.first-1; i>=0; i--) {
				if (grid[i][p.second] == 'x') {
					if (vis.find(make_pair(i+1, p.second)) == vis.end()) {
						nbound.insert(make_pair(i+1, p.second));
					}
					break;
				}
			}
			for (int i=p.first+1; i<h+2; i++) {
				if (grid[i][p.second] == 'x') {
					if (vis.find(make_pair(i-1, p.second)) == vis.end()) {
						nbound.insert(make_pair(i-1, p.second));
					}
					break;
				}
			}
			for (int i=p.second-1; i>=0; i--) {
				if (grid[p.first][i] == 'x') {
					if (vis.find(make_pair(p.first, i+1)) == vis.end()) {
						nbound.insert(make_pair(p.first, i+1));
					}
					break;
				}
			}
			for (int i=p.second+1; i<w+2; i++) {
				if (grid[p.first][i] == 'x') {
					if (vis.find(make_pair(p.first, i-1)) == vis.end()) {
						nbound.insert(make_pair(p.first, i-1));
					}
					break;
				}
			}
		}
		if (nbound.size() == 0) {
			break;
		}
		bound = nbound;
		nbound.clear();
		c++;
	}
	int out = INT_MAX;
	int score;
	for (auto i: vis1) {
		for (auto j: vis2) {
			if (i.first.first == j.first.first && i.first.second == j.first.second) {
				// cout << i.first.first << " " << i.first.second << " " << score << endl;
				score = i.second+j.second;
				if (score < out) {
					out = score;
				}
			}
		}
	}
	if (out == INT_MAX) {
		cout << "-1" << endl;
	} else {
		cout << out << endl;
	}
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40