## 11329 - Curious Fleas

Moderator: Board moderators

Loner
New poster
Posts: 3
Joined: Sat Sep 09, 2006 11:11 am

### 11329 - Curious Fleas

Help! What's wrong with my code? I can't find any mistakes.

Code: Select all

`` Delete After AC :) ``
Last edited by Loner on Mon Nov 05, 2007 6:12 pm, edited 1 time in total.

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
Heres some io test.

INPUT:

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
``````
OUTPUT:

Code: Select all

``````14
8
11
13
12
12
11
14
13
13
``````
----
Rio

Loner
New poster
Posts: 3
Joined: Sat Sep 09, 2006 11:11 am

### ...

Thanks a lot! What a stupid mistake!

just_yousef
New poster
Posts: 50
Joined: Tue Dec 17, 2013 11:01 pm

### Re: 11329 - Curious Fleas

In this problem,, if one of the die faces had a Flea on it and this face steps on a tile with another Flea,, what will happen??
and how many Fleas there will be at most in the square ??

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;
}
``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11329 - Curious Fleas

If the die rolls on a square containing a flea and the bottom of the die already had a flea on it, they would swap so that there is still one flea on the die and one flea on the square. There can not be more than one flea in a square or on a die face.
In my AC code I run BFS from every possible ending point to determine all reachable states before reading any input.
Check input and AC output for thousands of problems on uDebug!

just_yousef
New poster
Posts: 50
Joined: Tue Dec 17, 2013 11:01 pm

### Re: 11329 - Curious Fleas

I didn't figure out how to calculate all possible states before input

but I came up with this code But It Gives TLE

How can i use a hash function to make it faster ??

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;
}
``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11329 - Curious Fleas

There are 16 possible ending states: Each of the 16 squares with the die having one flea on each of it's 6 sides. I run BFS before I read the input, starting with each of those 16 ending states on the queue. I encode the state as an int: 4 bits are the die location, 6 bits for each of the die faces to indicate if it has a flea on it, and 16 bits to indicate if each square has a flea on it. I have a distance int array of size 1 << 26 = 67,108,864 (initialized to infinity) to keep track of how far away every reachable state is from an ending point. Now you work in reverse from the state on the front of the queue: decode the state from the int, then if:
1) There is a flea on the bottom of the die and not one in the current square - the flea jumps off the bottom of the die onto the square
2) There is not a flea on the bottom of the die and one in the current square - the flea jumps to the bottom of the die from the square
3) There is a flea on the bottom of the die and one in the current square - the fleas exchange position which doesn't affect the state in my code
4) There is not a flea on the bottom of the die and not one in the current square - no fleas move
Then try rolling the die in each of the 4 directions, then encode the state back to an int, if the next state hasn't been visited yet update the distance array and push that state onto the queue. Continue until the queue is empty.

Then I read the input, encode the state to an int, and see how far away that state is from an ending state or if it is not reachable.

I get AC in 1.1 seconds and my code is not optimized.
Check input and AC output for thousands of problems on uDebug!