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

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

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

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

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.

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

### Re: 11531 - Solve the Broken Maze

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

No.

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

thanks.

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

### Re: 11531 - Solve the Broken Maze

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

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

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

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.

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

### Re: 11531 - Solve the Broken Maze

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

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

### Re: 11531 - Solve the Broken Maze

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

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

### Re: 11531 - Solve the Broken Maze

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

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

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?