11531 - Solve the Broken Maze

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

Moderator: Board moderators

H_Hima
New poster
Posts: 18
Joined: Mon Sep 25, 2006 10:56 am
Location: Solar System
Contact:

11531 - Solve the Broken Maze

Post by H_Hima » Mon Oct 20, 2008 12:48 pm

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

LayCurse
New poster
Posts: 11
Joined: Sun Feb 25, 2007 3:14 pm
Location: Kyoto, Japan

Re: 11531 - Solve the Broken Maze

Post by LayCurse » Mon Oct 20, 2008 5:05 pm

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 :)
Last edited by LayCurse on Wed Oct 22, 2008 5:44 pm, edited 1 time in total.

H_Hima
New poster
Posts: 18
Joined: Mon Sep 25, 2006 10:56 am
Location: Solar System
Contact:

Re: 11531 - Solve the Broken Maze

Post by H_Hima » Mon Oct 20, 2008 6:40 pm

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

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

Re: 11531 - Solve the Broken Maze

Post by baodog » Tue Oct 21, 2008 12:44 am

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.

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Re: 11531 - Solve the Broken Maze

Post by emotional blind » Wed Oct 22, 2008 7:26 am

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?

H_Hima
New poster
Posts: 18
Joined: Mon Sep 25, 2006 10:56 am
Location: Solar System
Contact:

Re: 11531 - Solve the Broken Maze

Post by H_Hima » Thu Oct 23, 2008 10:16 am

No.

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

thanks.

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Re: 11531 - Solve the Broken Maze

Post by emotional blind » Fri Oct 24, 2008 4:28 am

Try the easier version of this problem.

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

LayCurse
New poster
Posts: 11
Joined: Sun Feb 25, 2007 3:14 pm
Location: Kyoto, Japan

Re: 11531 - Solve the Broken Maze

Post by LayCurse » Fri Oct 24, 2008 5:56 pm

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.

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

Re: 11531 - Solve the Broken Maze

Post by baodog » Fri Oct 24, 2008 10:45 pm

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!

LayCurse
New poster
Posts: 11
Joined: Sun Feb 25, 2007 3:14 pm
Location: Kyoto, Japan

Re: 11531 - Solve the Broken Maze

Post by LayCurse » Sat Oct 25, 2008 3:30 am

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.

User avatar
DemonCris
New poster
Posts: 25
Joined: Sun Feb 24, 2002 2:00 am
Location: Taiwan

Re: 11531 - Solve the Broken Maze

Post by DemonCris » Fri Jan 02, 2009 3:15 pm

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:

SerailHydra
New poster
Posts: 20
Joined: Mon Oct 20, 2008 6:26 am

Re: 11531 - Solve the Broken Maze

Post by SerailHydra » Sun Feb 15, 2009 9:32 am

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");
	}
}

User avatar
fushar
New poster
Posts: 26
Joined: Fri Apr 03, 2009 12:09 pm
Location: Indonesia
Contact:

Re: 11531 - Solve the Broken Maze

Post by fushar » Fri Jun 05, 2009 12:00 pm

I still don't get it...
What's the DP state for this problem?

DeadLock
New poster
Posts: 3
Joined: Thu Sep 24, 2009 2:05 am

Re: 11531 - Solve the Broken Maze

Post by DeadLock » Sun Oct 04, 2009 1:02 am

what is the correct answer for this case

Code: Select all

1
10
XXXBAAAAAA
XXXBAABBXX
XXXXXXBAXX
AAAAAAABAA
Thanks in advance

Leonid
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:

Re: 11531 - Solve the Broken Maze

Post by Leonid » Wed Nov 11, 2009 12:39 am

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?

Post Reply

Return to “Volume 115 (11500-11599)”