#include<bits/stdc++.h>
using namespace std;
const int maxh = 16, maxw = 16;
const int maxv = maxh * maxw;
struct robot{
int a, b;///a-lowest label, b-highest label
int wh;///position
robot(){
a = 0;
b = 0;
wh = -1;
}
robot(int _a, int _b, int _wh){
a = _a;
b = _b;
wh = _wh;
}
bool operator<(const robot &other)const{
if (a != other.a) return a < other.a;
if (b != other.b) return b < other.b;
return wh < other.wh;
}
};
int n, w, h;
vector<int> v[maxv];
string net[maxh];
vector<robot> rs;
int dir[4][maxh][maxw];
void speed(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
void read(){
cin >> n >> w >> h;
for (int i = 1; i <= h; ++i)
cin >> net[i];
}
bool is_valid_cell_to_pass(int i, int j){
if (i < 0 && h < i)
return false;
if (j < 0 && w < j)
return false;
if (net[i][j] == 'x')
return false;
return true;
}
int get_cell_num(int i, int j){
return i * h + j + 1;
}
int get_d(int i, int j, int d){
switch(net[i][j]){
case '.': break;
case '1': break;
case '2': break;
case '3': break;
case '4': break;
case '5': break;
case '6': break;
case '7': break;
case '8': break;
case '9': break;
case 'A': --d;
if (d == -1) d = 3;
break;
case 'C': ++d; d %= 4;
break;
default: assert(false);
}
return d;
}
pair<int, int> get_nextcell(int i, int j, int d){
pair<int, int> ret;
switch(d){
case 0: ret.first = i - 1;
ret.second = j;
break;
case 1: ret.first = i;
ret.second = j + 1;
break;
case 2: ret.first = i + 1;
ret.second = j;
break;
case 3: ret.first = i;
ret.second = j - 1;
break;
default: assert(false);
}
return ret;
}
inline void decode_net(){
for (int i = 0; i < h; ++i)
for (int j = 0; j < w; ++j)
for (int k = 0; k < 4; ++k){
if (dir[k][i][j]){
/*int cellnum = get_cell_num(i, j);
v[cellnum].push_back(dir[k][i][j]);*/
continue;
}
stack<pair<pair<int, int>, int> > cells;
pair<int, int> cur_cell = {i, j};
pair<int, int> next_cell;
cells.push({cur_cell, k});
int d;
do{
cur_cell = cells.top().first;
d = get_d(cur_cell.first, cur_cell.second, cells.top().second);
next_cell = get_nextcell(cur_cell.first, cur_cell.second, d);
cells.push({next_cell, d});
}while(!is_valid_cell_to_pass(next_cell.first, next_cell.second) &&
!dir[d][next_cell.first][next_cell.second]);
pair<int, int> occur_cell;
int occur_num;
if (!is_valid_cell_to_pass(next_cell.first, next_cell.second)){
cells.pop();
occur_cell = cells.top().first;
occur_num = get_cell_num(occur_cell.first, occur_cell.second);
}
else{
occur_cell = cells.top().first;
occur_num = dir[cells.top().second][occur_cell.first][occur_cell.second];
cells.pop();
}
while (!cells.empty()){
cur_cell = cells.top().first;
d = cells.top().second;
cells.pop();
dir[d][cur_cell.first][cur_cell.second] = occur_num;
int cur_num = get_cell_num(cur_cell.first, cur_cell.second);
v[cur_num].push_back(cur_num);
}
}
}
void inline find_start_positions(){
rs.resize(n);
for (int i = 0; i < h; ++i)
for (int j = 0; j < w; ++j)
if ('1' <= net[i][j] && net[i][j] <= '9'){
int numr = net[i][j] - '0';
int numcell = get_cell_num(i, j);
rs[numr].a = numr;
rs[numr].b = numr;
rs[numr].wh = numcell;
}
}
/*int availrobots(int exa, int exb, int wh){
for (int i = 0; i < (int)rs.size(); ++i){
auto r = rs[i];
if (r.a != exa && r.b != exb && r.wh == wh)
return i;
}
return -1;
}
void inline BFS(){
find_start_positions();
set<pair<int, int> > nonexistence;
map<robot, int> rpushes;
queue<robot> q;
for (auto r: rs){
q.push(r);
rpushes[r] = 0;
}
while (!q.empty() && (int)rs.size() > 1){
robot cur = q.front();
q.pop();
if (nonexistence.find({cur.a, cur.b}) != nonexistence.end())
continue;
int idxavailr = availrobots(cur.a, cur.b, cur.wh);
if (idxavailr != -1){
nonexistence.
}
for (auto nb: v[cur.wh])
}
}*/
int used[2][maxv];
void BFS_two_robots(){
find_start_positions();
queue<robot> q;
for (int i = 0; i < 2; ++i){
rs[i].a--;
rs[i].b--;
auto r = rs[i];
used[i ^ 1][r.wh] = 1;
q.push(r);
}
while (!q.empty()){
robot cur = q.front();
q.pop();
for (auto nb: v[cur.wh]){
used[cur.a][nb] = used[cur.a][cur.wh] + 1;
if (used[cur.a ^1][nb]){
cout << used[cur.a][nb] + used[cur.a ^ 1][nb] - 2;
return;
}
q.push(robot(cur.a, cur.b, nb));
}
}
}
int main(){
read();
decode_net();
BFS_two_robots();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
