11531 - Solve the Broken Maze

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

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

[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?
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));
}

{
/*	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");
}
}
``````
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?
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
``````