11329 - Curious Fleas

[Loner]

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

Code: Select all

 Delete After AC :) 

[rio]

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]

Thanks a lot! What a stupid mistake!

[just_yousef]

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 ??

here is my code, it prints impossible in all cases,, please help

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]

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.

[just_yousef]

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]

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.