11329 - Curious Fleas

All about problems in Volume 113. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

11329 - Curious Fleas

Post by Loner » Mon Nov 05, 2007 1:38 pm

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

Code: Select all

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

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Mon Nov 05, 2007 2:57 pm

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

...

Post by Loner » Mon Nov 05, 2007 6:12 pm

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

Post by just_yousef » Mon Jul 21, 2014 11:30 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11329 - Curious Fleas

Post by brianfry713 » Tue Jul 22, 2014 8:53 pm

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

Post by just_yousef » Thu Jul 24, 2014 11:03 am

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

Post by brianfry713 » Thu Jul 24, 2014 9:30 pm

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!

Post Reply

Return to “Volume 113 (11300-11399)”