
Code: Select all
Delete After AC :)
Moderator: Board moderators
Code: Select all
10
DX.X
.X..
..X.
X..X
...X
XXXX
D..X
....
XXX.
XX..
.DX.
....
DXX.
...X
...X
X..X
.X..
X.XD
.X.X
X...
.XX.
XX..
.DX.
X...
XXX.
XX..
.DX.
....
.XX.
...X
.XD.
X..X
.X..
XDX.
.X.X
X...
XX..
.X.D
..X.
X..X
Code: Select all
14
8
11
13
12
12
11
14
13
13
Code: Select all
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = a ; i < b;++i)
#define node pair<string, int>
int t, dir[8][4];
char grid[17];
map<node, bool> vist;
int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, 1, 0, -1 };
int valid(int x, int y) {
return (x >= 0 && y >= 0 && x < 4 && y < 4);
}
int bfs(int tx, int ty) {
int face, lev = 0;
node s1, s2;
vist.clear();
queue<node> que;
s1.first = grid;
s1.second = 0;
que.push(s1);
vist[s1] = 1;
while (que.size()) {
int s = que.size();
while (s--) {
s1 = que.front();
que.pop();
string tmp = s1.first;
int msk = s1.second, y, x;
rep(i,0,4) {
rep(j,0,4) {
//cout << tmp[i * 4 + j];
char ch = tmp[i * 4 + j];
if ((ch > '0' && ch < '7') || (ch > 'X')) {
x = i, y = j;
}
}
//cout << endl;
}
if (tmp[x * 4 + y] > '0' && tmp[x * 4 + y] < '9') {
face = tmp[x * 4 + y] - '0';
} else {
face = tmp[x * 4 + y] - 'X';
}
tmp[x * 4 + y] = '.';
for (int i = 0; i < 4; ++i) {
int _msk = msk, _face = dir[face][i], _x = x + dx[i], _y = y
+ dy[i];
string ss = tmp;
if (!valid(_x, _y))
continue;
if (msk & (1 << _face)) {
ss[_x * 4 + _y] = 'X' + _face;
} else {
if (ss[_x * 4 + _y] != '.') {
_msk |= (1 << _face);
}
ss[_x * 4 + _y] = _face + '0';
}
/*rep(i,0,4) {
rep(j,0,4)
cout << ss[i * 4 + j];
cout << endl;
}
cout << endl;*/
if (vist[make_pair(ss, _msk)])
continue;
if (_msk == (1 << 6) - 1) {
return lev + 1;
}
vist[make_pair(ss, _msk)] = 1;
que.push(make_pair(ss, _msk));
}
}
lev++;
}
return -1;
}
int main(int argc, char **argv) {
// freopen("a.in", "r", stdin);
dir[1][0] = 5; //forword
dir[1][1] = 4; //right
dir[1][2] = 3; //left
dir[1][3] = 2; //backword
dir[2][0] = 1;
dir[2][1] = 4;
dir[2][2] = 3;
dir[2][3] = 6;
dir[3][0] = 5;
dir[3][1] = 1;
dir[3][2] = 6;
dir[3][3] = 2;
dir[4][0] = 2;
dir[4][1] = 6;
dir[4][2] = 1;
dir[4][3] = 5;
dir[5][0] = 6;
dir[5][1] = 4;
dir[5][2] = 3;
dir[5][3] = 1;
dir[6][0] = 2;
dir[6][1] = 4;
dir[6][2] = 3;
dir[6][3] = 5;
int tx, ty;
scanf("%d", &t);
while (t--) {
rep(i,0,4) {
rep(j,0,4) {
scanf(" %c", &grid[i * 4 + j]);
if (grid[i * 4 + j] == 'D')
tx = i, ty = j, grid[i * 4 + j] = '1';
}
}
int ans = bfs(tx, ty);
if (ans == -1)
puts("impossible");
else
printf("%d\n", ans);
}
return 0;
}
Code: Select all
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = a ; i < b;++i)
int t;
pair<int, int> dir[8][8][4];
char grid[18];
map<string, int> vist;
int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, 1, 0, -1 };
int valid(int x, int y) {
return (x >= 0 && y >= 0 && x < 4 && y < 4);
}
int bfs() {
queue<string> que;
que.push(grid);
vist.clear();
vist[grid] = 0;
string tmp, ss;
int face, x, y, _x, _y, _face, msk, _msk, lev = 0, front;
char ch;
while (que.size()) {
int s = que.size();
while (s--) {
tmp = que.front();
front = tmp[16] - '0';
que.pop();
msk = vist[tmp];
rep(i,0,4) {
rep(j,0,4) {
ch = tmp[i * 4 + j];
if ((ch >= '0' && ch <= '9') || (ch > 'X')) {
x = i, y = j;
goto prt;
}
}
}
prt: ;
if (ch > 'X') {
face = ch - 'X';
ch = 'X';
} else {
face = ch - '0';
ch = '.';
}
tmp[x * 4 + y] = ch;
for (int i = 0; i < 4; ++i) {
_x = x + dx[i], _y = y + dy[i];
if (!valid(_x, _y))
continue;
ss = tmp;
_face = dir[face][front][i].first;
_msk = msk;
ss[16] = dir[face][front][i].second + '0';
if (_msk & (1 << _face)) {
if (ss[_x * 4 + y] != 'X')
_msk &= ~(1 << _face);
ss[_x * 4 + _y] = 'X' + _face;
} else {
if (ss[_x * 4 + _y] == 'X')
_msk |= (1 << _face);
ss[_x * 4 + _y] = '0' + _face;
}
if (vist.find(ss) != vist.end())
continue;
if (_msk == 126)
return lev + 1;
vist[ss] = _msk;
que.push(ss);
}
}
lev++;
}
return -1;
}
int main(int argc, char **argv) {
//freopen("a.in", "r", stdin);
//indices are the current face on the floor,
//the face number heading forword,and the direction of the turn
//pair<the next face which will be on the floor, and the face will be heading forward
dir[1][2][0] = make_pair(2, 6);
dir[1][2][1] = make_pair(3, 2);
dir[1][2][2] = make_pair(5, 1);
dir[1][2][3] = make_pair(4, 2);
dir[1][3][0] = make_pair(3, 6);
dir[1][3][1] = make_pair(5, 3);
dir[1][3][2] = make_pair(4, 1);
dir[1][3][3] = make_pair(2, 3);
dir[1][5][0] = make_pair(5, 6);
dir[1][5][1] = make_pair(4, 5);
dir[1][5][2] = make_pair(2, 1);
dir[1][5][3] = make_pair(3, 5);
dir[1][4][0] = make_pair(4, 6);
dir[1][4][1] = make_pair(2, 4);
dir[1][4][2] = make_pair(3, 1);
dir[1][4][3] = make_pair(5, 4);
///////////////////////////
dir[2][6][0] = make_pair(6, 5);
dir[2][6][1] = make_pair(3, 6);
dir[2][6][2] = make_pair(1, 2);
dir[2][6][3] = make_pair(4, 6);
dir[2][3][0] = make_pair(3, 5);
dir[2][3][1] = make_pair(1, 3);
dir[2][3][2] = make_pair(4, 2);
dir[2][3][3] = make_pair(6, 3);
dir[2][1][0] = make_pair(1, 5);
dir[2][1][1] = make_pair(4, 1);
dir[2][1][2] = make_pair(6, 2);
dir[2][1][3] = make_pair(3, 1);
dir[2][4][0] = make_pair(4, 5);
dir[2][4][1] = make_pair(6, 4);
dir[2][4][2] = make_pair(3, 2);
dir[2][4][3] = make_pair(1, 4);
//////////////////////////
dir[3][1][0] = make_pair(1, 4);
dir[3][1][1] = make_pair(2, 1);
dir[3][1][2] = make_pair(6, 3);
dir[3][1][3] = make_pair(5, 1);
dir[3][2][0] = make_pair(2, 4);
dir[3][2][1] = make_pair(6, 2);
dir[3][2][2] = make_pair(5, 3);
dir[3][2][3] = make_pair(1, 2);
dir[3][6][0] = make_pair(6, 4);
dir[3][6][1] = make_pair(5, 6);
dir[3][6][2] = make_pair(1, 3);
dir[3][6][3] = make_pair(2, 6);
dir[3][5][0] = make_pair(5, 4);
dir[3][5][1] = make_pair(1, 5);
dir[3][5][2] = make_pair(2, 3);
dir[3][5][3] = make_pair(6, 5);
/////////////////////////
dir[4][2][0] = make_pair(2, 3);
dir[4][2][1] = make_pair(1, 2);
dir[4][2][2] = make_pair(5, 4);
dir[4][2][3] = make_pair(6, 2);
dir[4][1][0] = make_pair(1, 3);
dir[4][1][1] = make_pair(5, 1);
dir[4][1][2] = make_pair(6, 4);
dir[4][1][3] = make_pair(2, 1);
dir[4][5][0] = make_pair(5, 3);
dir[4][5][1] = make_pair(6, 5);
dir[4][5][2] = make_pair(2, 4);
dir[4][5][3] = make_pair(1, 5);
dir[4][6][0] = make_pair(6, 3);
dir[4][6][1] = make_pair(2, 6);
dir[4][6][2] = make_pair(1, 4);
dir[4][6][3] = make_pair(5, 6);
/////////////////////////
dir[5][3][0] = make_pair(3, 2);
dir[5][3][1] = make_pair(6, 3);
dir[5][3][2] = make_pair(4, 5);
dir[5][3][3] = make_pair(1, 3);
dir[5][6][0] = make_pair(6, 2);
dir[5][6][1] = make_pair(4, 6);
dir[5][6][2] = make_pair(1, 5);
dir[5][6][3] = make_pair(3, 6);
dir[5][4][0] = make_pair(4, 2);
dir[5][4][1] = make_pair(1, 4);
dir[5][4][2] = make_pair(3, 5);
dir[5][4][3] = make_pair(6, 4);
dir[5][1][0] = make_pair(1, 2);
dir[5][1][1] = make_pair(3, 1);
dir[5][1][2] = make_pair(6, 5);
dir[5][1][3] = make_pair(4, 1);
/////////////////////////
dir[6][2][0] = make_pair(2, 1);
dir[6][2][1] = make_pair(4, 2);
dir[6][2][2] = make_pair(5, 6);
dir[6][2][3] = make_pair(3, 2);
dir[6][4][0] = make_pair(4, 1);
dir[6][4][1] = make_pair(5, 4);
dir[6][4][2] = make_pair(3, 6);
dir[6][4][3] = make_pair(2, 4);
dir[6][5][0] = make_pair(5, 1);
dir[6][5][1] = make_pair(3, 5);
dir[6][5][2] = make_pair(2, 6);
dir[6][5][3] = make_pair(4, 5);
dir[6][3][0] = make_pair(3, 1);
dir[6][3][1] = make_pair(2, 3);
dir[6][3][2] = make_pair(4, 6);
dir[6][3][3] = make_pair(5, 3);
scanf("%d", &t);
while (t--) {
rep(i,0,4) {
rep(j,0,4) {
scanf(" %c", &grid[i * 4 + j]);
if (grid[i * 4 + j] == 'D')
grid[i * 4 + j] = '6';
}
}
grid[16] = '5';
int ans = bfs();
if (ans == -1)
puts("impossible");
else
printf("%d\n", ans);
}
return 0;
}