Page 1 of 2

### 11531 - Solve the Broken Maze

Posted: 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.
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
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

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
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
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
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
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
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
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
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...)
--------------------------

[EDIT] I confused rows and columns.

### Re: 11531 - Solve the Broken Maze

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

### Re: 11531 - Solve the Broken Maze

Posted: 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));
}

{
/*	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)
{
if (!State[i][0] && State[i][4])
{
}
else if (State[i][0] && !State[i][4])
{
}
else if (State[i][0] && State[i][4])
{
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
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
what is the correct answer for this case

Code: Select all

``````1
10
XXXBAAAAAA
XXXBAABBXX
XXXXXXBAXX
AAAAAAABAA
``````