Page 1 of 2

11531 - Solve the Broken Maze

Posted: Mon Oct 20, 2008 12:48 pm
by H_Hima
Hi.

May any one help me in my wrong?
this code got WA.

I used bfs one board by cosidering 4 different ways to enter each block.

this is my code.
please help me.
thanks.

Code: Select all

#include<iostream>
#include<fstream>
#include<algorithm>
#include<stdio.h>
#include<strstream>
using namespace std;

char blocks[100000][4];
char paths[100000][4];
bool gone[100000][4][4];

struct pos{
	int c,r,dir;
};

pos path[1000000];

int n;

int valid(pos p) {
	if(p.r<0||p.r>=4||p.c<0)
		return 0;
	if(p.c>=n)
		return 2;
	if(gone[p.r][p.c][p.dir]||blocks[p.r][p.c]=='X')
		return 0;
	gone[p.r][p.c][p.dir]=true;
	return 1;
}

bool bfs() {
	int i,j,k,cnt=0;
	pos nex;
	for(j=0;j<n;j++)
		for(i=0;i<4;i++)
			for(k=0;k<4;k++)
				gone[i][j][k]=false;
	for(i=0;i<4;i++) {
		if(blocks[i][0]=='A') {
			path[cnt].c=0;
			path[cnt].r=i;
			path[cnt++].dir=0;
			gone[i][0][0]=gone[i][0][1]=true;
		}
		if(blocks[i][0]=='B') {
			path[cnt].c=0;
			path[cnt].r=i;
			path[cnt++].dir=0;
			gone[i][0][0]=true;
		}
	}
	pos cur;
	for(i=0;i<cnt;i++) {
		cur=path[i];
		if(blocks[cur.r][cur.c]=='A') {
			if(cur.dir==0) {
				nex=cur;
				nex.c++;
				if(k=valid(nex)) {
					if(k==2)
						return true;
					path[cnt++]=nex;
				}
			}
			else if(cur.dir==1) {
				nex=cur;
				nex.c--;
				if(k=valid(nex)) {
					path[cnt++]=nex;
				}
			}
			else if(cur.dir==2) {
				nex=cur;
				nex.r++;
				if(k=valid(nex)) {
					path[cnt++]=nex;
				}
			}
			else if(cur.dir==3) {
				nex=cur;
				nex.r--;
				if(k=valid(nex)) {
					path[cnt++]=nex;
				}
			}
		}
		if(blocks[cur.r][cur.c]=='B') {
			if(cur.dir==0||cur.dir==1) {
				nex=cur;
				nex.r--;
				nex.dir=3;
				if(k=valid(nex)) {
					path[cnt++]=nex;
				}
				
				nex=cur;
				nex.r++;
				nex.dir=2;
				if(k=valid(nex)) {
					path[cnt++]=nex;
				}
			}
			else if(cur.dir==2||cur.dir==3) {
				nex=cur;
				nex.c--;
				nex.dir=1;
				if(k=valid(nex)) {
					path[cnt++]=nex;
				}
				
				nex=cur;
				nex.c++;
				nex.dir=0;
				if(k=valid(nex)) {
					if(k==2)
						return true;
					path[cnt++]=nex;
				}
			}
		}
	}
	return false;
}

int main() {
	//ifstream cin("input.txt");
	int i,j,k,t;
	cin>>t;
	while(t--) {
		cin>>n;
		for(j=0;j<4;j++) {
			//for(i=0;i<n;i++) {
				cin>>blocks[j];
			//}
		}
		if(bfs())
			cout<<"Try."<<endl;
		else
			cout<<"Don't Try."<<endl;
	}
}

Re: 11531 - Solve the Broken Maze

Posted: Mon Oct 20, 2008 5:05 pm
by LayCurse
Try these cases.
3
10
XXXBAAAAAA
XXXBAAABXX
XXXXXXBAXX
AAAAAAABAA
4
XBBX
AABA
XBBX
XXXX
7
AABBABX
XBAAABX
XBAAAAA
XXBBXXX
Correct answers may be "Try." & "Don't Try." & "Don't Try."

I cannnot solve this problem correctly too.
I have no idea..., can anyone give me some advice? TIA :)

Re: 11531 - Solve the Broken Maze

Posted: Mon Oct 20, 2008 6:40 pm
by H_Hima
Thanks for your help.

the first testcase give an error because of a simple wrong in dimensions of array.
but the second one was the Big one.
the bfs can't solve this problem.

I used DFS but got TLE. and this is the dfs code.

it's clear that why it got TLE but what's the solution?

may any one help?

Code: Select all

#include<iostream>
#include<fstream>
#include<algorithm>
#include<stdio.h>
#include<strstream>
using namespace std;

char blocks[4][100000];
char paths[100000][4];
//bool gone[4][100000][4];

bool used[4][100000];
bool dfsused[1000000];

struct pos{
	int c,r,dir;
	bool nn[4];
};

pos path[1000000];

int n;

int valid(pos p) {
	if(p.r<0||p.r>=4||p.c<0)
		return 0;
	if(p.c>=n)
		return 2;
	if(/*gone[p.r][p.c][p.dir]||*/blocks[p.r][p.c]=='X'||used[p.r][p.c])
		return 0;
	used[p.r][p.c]=true;
	//gone[p.r][p.c][p.dir]=true;
	return 1;
}

pos blk;

bool dfs(pos start) {
	int i,j,k,cnt=1;
	pos nex;
	pos cur;
	path[0]=start;
	used[start.r][start.c]=true;
	path[0].nn[0]=path[0].nn[1]=path[0].nn[2]=path[0].nn[3]=true;
	for(i=0;i>=0;) {
		cur=path[i];
		if(blocks[cur.r][cur.c]=='A') {
			if(path[i].nn[0]&&cur.dir==0) {
				nex=cur;
				nex.c++;
				if(k=valid(nex)) {
					if(k==2)
						return true;
					nex.nn[0]=nex.nn[1]=nex.nn[2]=nex.nn[3]=true;
					path[i].nn[0]=false;
					i++;
					path[i]=nex;
					continue;
				}
			}
			else if(path[i].nn[1]&&cur.dir==1) {
				nex=cur;
				nex.c--;
				if(k=valid(nex)) {
					nex.nn[0]=nex.nn[1]=nex.nn[2]=nex.nn[3]=true;
					path[i].nn[1]=false;
					i++;
					path[i]=nex;
					continue;
				}
			}
			else if(path[i].nn[2]&&cur.dir==2) {
				nex=cur;
				nex.r++;
				if(k=valid(nex)) {
					nex.nn[0]=nex.nn[1]=nex.nn[2]=nex.nn[3]=true;
					path[i].nn[2]=false;
					i++;
					path[i]=nex;
					continue;
				}
			}
			else if(path[i].nn[3]&&cur.dir==3) {
				nex=cur;
				nex.r--;
				if(k=valid(nex)) {
					nex.nn[0]=nex.nn[1]=nex.nn[2]=nex.nn[3]=true;
					path[i].nn[3]=false;
					i++;
					path[i]=nex;
					continue;
				}
			}
		}
		if(blocks[cur.r][cur.c]=='B') {
			if(cur.dir==0||cur.dir==1) {
				if(path[i].nn[0]) {
					nex=cur;
					nex.r--;
					nex.dir=3;
					if(k=valid(nex)) {
						nex.nn[0]=nex.nn[1]=nex.nn[2]=nex.nn[3]=true;
						path[i].nn[0]=false;
						i++;
						path[i]=nex;
						continue;
					}
				}
				if(path[i].nn[1]) {
					nex=cur;
					nex.r++;
					nex.dir=2;
					if(k=valid(nex)) {
						nex.nn[0]=nex.nn[1]=nex.nn[2]=nex.nn[3]=true;
						path[i].nn[1]=false;
						i++;
						path[i]=nex;
						continue;
					}
				}
			}
			else if(cur.dir==2||cur.dir==3) {
				if(path[i].nn[2]) {
					nex=cur;
					nex.c--;
					nex.dir=1;
					if(k=valid(nex)) {
						nex.nn[0]=nex.nn[1]=nex.nn[2]=nex.nn[3]=true;
						path[i].nn[2]=false;
						i++;
						path[i]=nex;
						continue;
					}
				}
				if(path[i].nn[3]) {
					nex=cur;
					nex.c++;
					nex.dir=0;
					if(k=valid(nex)) {
						if(k==2)
							return true;
						nex.nn[0]=nex.nn[1]=nex.nn[2]=nex.nn[3]=true;
						path[i].nn[3]=false;
						i++;
						path[i]=nex;
						continue;
					}
				}
			}
		}
		used[path[i].r][path[i].c]=false;
		i--;
	}
	return false;
}

bool dfsinit() {
	memset(dfsused,true,sizeof(dfsused));
	int i,j,k,cnt=0;
	pos nex;
	for(j=0;j<n;j++)
		for(i=0;i<4;i++) {
			used[i][j]=false;
			//for(k=0;k<4;k++)
				//gone[i][j][k]=false;
		}
	for(i=0;i<4;i++) {
		if(blocks[i][0]=='A') {
			nex.c=0;
			nex.r=i;
			nex.dir=0;
			//gone[i][0][0]=gone[i][0][1]=true;
			if(dfs(nex))
				return true;
		}
		if(blocks[i][0]=='B') {
			nex.c=0;
			nex.r=i;
			nex.dir=0;
			//gone[i][0][0]=true;
			if(dfs(nex))
				return true;
		}
	}
	return false;
}


int main() {
	//freopen("input.txt","r",stdin);
	int i,j,k,t;
	scanf("%d",&t);
	while(t--) {
		scanf("%d",&n);
		for(j=0;j<4;j++) {
			//for(i=0;i<n;i++) {
				scanf("%s",blocks[j]);
			//}
		}
		if(dfsinit())
			cout<<"Try."<<endl;
		else
			cout<<"Don't Try."<<endl;
	}
}

Re: 11531 - Solve the Broken Maze

Posted: Tue Oct 21, 2008 12:44 am
by baodog
You want to use profile DP. For use brute force on a 4x(4!) grid, then do DP from there.
I still get wa though.

Re: 11531 - Solve the Broken Maze

Posted: Wed Oct 22, 2008 7:26 am
by emotional blind
LayCurse wrote:I cannnot solve this problem correctly too.
I have no idea..., can anyone give me some advice? TIA :)

The idea is DP. Did you try with DP?

Re: 11531 - Solve the Broken Maze

Posted: Thu Oct 23, 2008 10:16 am
by H_Hima
No.

I can't understand the DP solution.
may you explain more?

thanks.

Re: 11531 - Solve the Broken Maze

Posted: Fri Oct 24, 2008 4:28 am
by emotional blind
Try the easier version of this problem.

https://www.spoj.pl/problems/MAZE/

Re: 11531 - Solve the Broken Maze

Posted: Fri Oct 24, 2008 5:56 pm
by LayCurse
Finally, I managed to get AC! :)
Indeed the solution is DP, but it is a bit difficult and complex for me (without help).
Thanks for help.

Re: 11531 - Solve the Broken Maze

Posted: Fri Oct 24, 2008 10:45 pm
by baodog
Hi Laycurse,

Would you be willing to describe your solution a little?
I tried 4^4 states per column, and handling 256*256 state transitions,
but is too slow. How do you handle the states? How do you
go to the left after you have gone to the right in your DP? Thanks!

Re: 11531 - Solve the Broken Maze

Posted: Sat Oct 25, 2008 3:30 am
by LayCurse
In my DP, I culculate all possible states from 1st column to k-th column using all possible states from 1st column to (k-1)-st column,
where states have 8 elements, for example, states (from 1st column to k-th column) have information that is
  • if we go right 2nd row from left of 1st column, where we arrive (or path is not continued)
  • if we go left 4th row from right of k-th column, where we arrive (or path is not continued)
and so on.

After ignoring meaningless states, number of states may be about 50. (It is unsure...)
--------------------------
Sorry for my bad English and bad explanation, hope it help.

[EDIT] I confused rows and columns.

Re: 11531 - Solve the Broken Maze

Posted: Fri Jan 02, 2009 3:15 pm
by DemonCris
Hi LayCurse,

I still don't get it.
When we talk about the k-th column, there is a case that the route may bend back to (k-1)th column and return back to k-th column.
In this case, how do you represent your DP formula?
For example, consider the following maze,

????
????
????
????

In this case, the route will bend back to 3rd column after it goes to 4-th column. How do you handle this kind of case?
Thanks for anyone's reply :lol:

Re: 11531 - Solve the Broken Maze

Posted: Sun Feb 15, 2009 9:32 am
by SerailHydra
Is there anyone who can provide some tests for me? I got so many WAs.

Here is my code:

Code: Select all

#include <iostream>

using namespace std;

#define MaxN 20005
#define MaxSize 200
#define MaxHash 300000

typedef int List[6];
int Test, N, Total = 0;
char Map[4][MaxN];
List E, State[MaxSize];
int Serial[MaxHash], Transfer[MaxSize][7];
bool V[4][MaxN][MaxSize];

int Encode(List E)
{
	int Result = 0;
	for (int i = 4; i >= 0; -- i)
		Result = (Result << 3) + E[i];
	return (Result << 4) + E[5];
}

void Enumerate(int D, int Limit)
{
	if (D == Limit)
	{
		if (!E[5]) return;
		for (int i = 0; i < 6; ++ i)
			State[Total][i] = E[i];
/*		for (int i = 0; i < 6; ++ i)
			printf("%d ", E[i]);
		printf("%d\n", Encode(E));
*/		Serial[Encode(E)] = Total ++;
		return;
	}
	int Num = 0;
	for (int i = 0; i < 5; ++ i)
		if (E[i] == D) ++ Num;
	Enumerate(D + 1, Limit);
	if (Num == 1)
	{
		E[5] += 1 << (D - 1);
		Enumerate(D + 1, Limit);
		E[5] -= 1 << (D - 1);
	}
}

void Search(int D, int Limit)
{
	if (D == 5)
	{
		if (E[3] && E[4] && E[3] != E[4]) return;
		for (int i = 0; i < 5; ++ i)
			if (E[i])
				for (int j = i + 2; j < 5; ++ j)
					if (E[j] == E[i])
						for (int k = i + 1; k < j; ++ k)
						{
							if (E[k] == E[i]) return;
							if (E[k] && E[k] != E[i])
								for (int l = j + 1; l < 5; ++ l)
									if (E[k] == E[l]) return;
						}
		E[5] = 0;
		Enumerate(1, Limit);
		return;
	}
	for (int i = 0; i <= Limit; ++ i)
	{
		E[D] = i;
		Search(D + 1, max(Limit, i + 1));
	}
}

void MinExp(List &S)
{
	List T;
	memset(T, -1, sizeof(T));
	T[5] = 0;
	int Q = 0;
	for (int i = 0; i < 5; ++ i)
		if (!S[i]) T[i] = 0;
		else if (T[i] == -1)
		{
			if (S[5] & (1 << (S[i] - 1))) T[5] += 1 << Q;
			T[i] = ++ Q;
			for (int j = i + 1; j < 5; ++ j)
				if (S[i] == S[j]) T[j] = Q;
		}
	memcpy(S, T, sizeof(T));
}

void Add(int i, int Type)
{
/*	printf("%d Type %d: ", i, Type);
	for (int j = 0; j < 6; ++ j)
		printf("%d ", State[i][j]);
	printf("-> ");
*/	for (int j = 1; j < 5; ++ j)
		E[j - 1] = State[i][j];
	E[5] = State[i][5];
	if (!Type) E[3] = E[4] = 0;
	else if (Type == 1) E[3] = State[i][0], E[4] = 0;
	else if (Type == 2) E[3] = 0, E[4] = State[i][4];
	else if (Type == 3)
	{
		for (int j = 0; j < 5; ++ j)
			if (E[j] == State[i][4]) E[j] = State[i][0];
		E[3] = E[4] = 0;
		if (!(E[5] & (1 << (State[i][0] - 1)))) E[5] |= 1 << (State[i][0] - 1);
		if (!(E[5] & (1 << (State[i][4] - 1)))) E[5] |= 1 << (State[i][4] - 1);
	}
	else if (Type == 4) E[3] = 0, E[4] = State[i][0];
	else if (Type == 5) E[3] = E[4] = 5;
	else if (Type == 6) E[3] = State[i][4], E[4] = 0;
	MinExp(E);
/*	for (int j = 0; j < 6; ++ j)
		printf("%d ", E[j]);
	printf("\n");
*/	Transfer[i][Type] = Serial[Encode(E)];
}

void Update(int i, int j, int k)
{
	if (k == -1) return;
	if (i == 4) i = 0, ++ j;
	V[i][j][k] = 1;
}

bool Solve()
{
	memset(V, 0, sizeof(V));
	V[0][0][Serial[36127]] = 1;
	for (int j = 0; j < N; ++ j)
	{
		if (Map[0][j] == 'A')
			for (int k = 0; k < Total; ++ k)
				if (V[0][j][k]) Update(1, j, Transfer[k][1]);
		if (Map[0][j] == 'B')
			for (int k = 0; k < Total; ++ k)
				if (V[0][j][k])
				{
					Update(1, j, Transfer[k][4]);
					Update(1, j, Transfer[k][5]);
				}
		for (int k = 0; k < Total; ++ k)
			if (V[0][j][k]) Update(1, j, Transfer[k][0]);
		for (int i = 1; i < 4; ++ i)
		{
			if (Map[i][j] == 'A')
				for (int k = 0; k < Total; ++ k)
					if (V[i][j][k])
						for (int l = 1; l < 3; ++ l)
							Update(i + 1, j, Transfer[k][l]);
			if (Map[i][j] == 'B')
				for (int k = 0; k < Total; ++ k)
					if (V[i][j][k])
						for (int l = 3; l < 7; ++ l)
							Update(i + 1, j, Transfer[k][l]);
			for (int k = 0; k < Total; ++ k)
				if (V[i][j][k]) Update(i + 1, j, Transfer[k][0]);
		}
	}
/*	for (int i = 0; i < Total; ++ i)
		if (V[2][3][i])
		{
			for (int j = 0; j < 6; ++ j)
				printf("%d ", State[i][j]);
			printf("%d\n", Serial[Encode(State[i])]);
		}
*/	for (int i = 0; i < Total; ++ i)
		if (V[0][N][i])
			for (int j = 0; j < 4; ++ j)
				if (State[i][j] && (State[i][5] & (1 << (State[i][j] - 1)))) return 1;
	return 0;
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("UVa.in", "r", stdin);
	freopen("UVa.out", "w", stdout);
#endif
	memset(Serial, -1, sizeof(Serial));
	Total = 0;
	Search(0, 1);
	memset(Transfer, -1, sizeof(Transfer));
	for (int i = 0; i < Total; ++ i)
	{
		Add(i, 0);
		Add(i, 5);
		if (!State[i][0] && State[i][4])
		{
			Add(i, 2);
			Add(i, 6);
		}
		else if (State[i][0] && !State[i][4])
		{
			Add(i, 1);
			Add(i, 4);
		}
		else if (State[i][0] && State[i][4])
		{
			Add(i, 1);
			Add(i, 2);
			Add(i, 4);
			Add(i, 6);
			if (State[i][0] != State[i][4]) Add(i, 3);
		}
	}
	scanf("%d", &Test);
	for (; Test --; )
	{
		scanf("%d\n", &N);
		for (int i = 0; i < 4; ++ i)
			gets(Map[i]);
		if (Solve()) printf("Try.\n");
		else printf("Don’t Try.\n");
	}
}

Re: 11531 - Solve the Broken Maze

Posted: Fri Jun 05, 2009 12:00 pm
by fushar
I still don't get it...
What's the DP state for this problem?

Re: 11531 - Solve the Broken Maze

Posted: Sun Oct 04, 2009 1:02 am
by DeadLock
what is the correct answer for this case

Code: Select all

1
10
XXXBAAAAAA
XXXBAABBXX
XXXXXXBAXX
AAAAAAABAA
Thanks in advance

Re: 11531 - Solve the Broken Maze

Posted: Wed Nov 11, 2009 12:39 am
by Leonid
I'm getting WA so far for this task and I'm not sure I understand the task correctly. Can we actually travel via the same block more than once? I.e. move - rotate - move. I think the question above (by DeadLock) asks the same. If it were the case, then the task is pretty much DFS in O(N). So I don't think this is a case, and I wrote the code which looks up if it is possible to find a fixed maze, without ever visiting the same block more than once (which is a far more difficult task), but it gets WA. Could anyone with AC sort out the solution for the case above?