| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 113656 |
2019-05-27T12:15:22 Z |
sahil_k |
Robots (APIO13_robots) |
C++14 |
|
2 ms |
384 KB |
#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 = max(i.second, j.second);
if (score < out) {
out = score;
}
}
}
}
if (out == INT_MAX) {
cout << "-1" << endl;
} else {
cout << out << endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
