258 - Mirror Maze

[broderic]

Hello,
I've gotten several WA's for this problem but I can't figure out why.
I'd hate to post code but I don't see any other way...
can anybody think of a test case where this code will fail?

The algorithm i used is this:
- dfs from one mirror to the next flipping the mirrors correctly as we go.
if it is the first time we've encountered this mirror, we set it's locked variable to 1.
- since each mirror has two reflective sides, it may be neccessary to
reflect off a mirror that has already been encountered. if we encounter
a mirror with its lock set to 1, we set it to 2.
- if we encounter a mirror with its lock set to 2, we don't go to it because
then we'd enter an infite loop.
- keep going till we hit the exit.

Here's my code (excuse the mess):
[c]
#include <stdio.h>
#include <string.h>

int M,N,sx,sy,ex,ey;
char maze[52][52];
char locked[52][52];

typedef enum{down,up,right,left,dnum} dtype_t;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

void printmaze() {
int i,j;
for (i=1; i<=N; i++) {
for (j=1; j<=M; j++) printf("%c", maze[j]);
printf("\n");
}
}

int mirror(char a) {return (a=='/'||a=='\\')?1:0;}

int search(int *x, int *y, int dir) {
while (1) {
if (mirror(maze[*y][*x]) || (*x==ex && *y==ey)) {
if (locked[*y][*x]==2) return 0;
else return 1;
}
if (maze[*y][*x]=='*') return 0;
*x += dx[dir];
*y += dy[dir];
}
return 0;
}
int dfs(int x, int y, int in) {
int i,j,dir,end,go1=1,go2=1;

if (x==ex && y==ey) return 1;

if (in<=up) {
i=x+1; j=y;
if (locked[y][x]) {
if (in==up && maze[y][x]=='/') go2=0;
if (in==up && maze[y][x]=='\\') go1=0;
if (in==down && maze[y][x]=='/') go1=0;
if (in==down && maze[y][x]=='\\') go2=0;
}
if (go1 && search(&i, &j, right)) {
if (mirror(maze[y][x])) maze[y][x] = (in==up)?'/':'\\';
locked[y][x]++;
if (dfs(i,j,right)) return 1;
}
i=x-1; j=y;
if (go2 && search(&i, &j, left)) {
if (mirror(maze[y][x])) maze[y][x] = (in==up)?'\\':'/';
locked[y][x]++;
if (dfs(i,j,left)) return 1;
}
} else {
i=x; j=y-1;
if (locked[y][x]) {
if (in==left && maze[y][x]=='/') go1=0;
if (in==left && maze[y][x]=='\\') go2=0;
if (in==right && maze[y][x]=='/') go2=0;
if (in==right && maze[y][x]=='\\') go1=0;
}

if (search(&i,&j,up)) {
if (mirror(maze[y][x])) maze[y][x] = (in==right)?'/':'\\';
locked[y][x]++;
if (dfs(i,j,up)) return 1;
}
i=x; j=y+1;
if (search(&i,&j,down)) {
if (mirror(maze[y][x])) maze[y][x] = (in==right)?'\\':'/';
locked[y][x]++;
if (dfs(i,j,down)) return 1;
}
}
locked[y][x]--;
return 0;
}
int main () {
int i,j,cnum=1,dir;

while (scanf("%d %d ", &M, &N)==2) {
if (M==-1 && N==-1) break;
memset(maze,'*',sizeof(maze));
for (i=1; i<=N; i++) {
gets(&maze[1]);
maze[M+1]='*';
}
for (i=1,sx=-1; i<=N; i+=N-1)
for (j=1; j<=M; j++) {
if (maze[j]=='.') {
if (sx==-1) { sx=j; sy=i; }
else {ex=j; ey=i; }
}
}
for (i=1; i<=M; i+=M-1)
for (j=1; j<=N; j++) {
if (maze[j]=='.') {
if (sx==-1) {sx=i; sy=j; }
else {ex=i; ey=j;}
}
}

if (sx==1) dir=up;
else if (sx==M) dir=up;
else if (sy==1) dir=right;
else if (sy==N) dir=right;
memset(locked,0,sizeof(locked));
dfs(sx,sy,dir);
if (cnum++>1) printf("\n");
printmaze();
}
return 0;
}[/c]

[afonsocsc]

your program fails with this input:

Code: Select all

10 10
**********
*\........
*..\....\*
*/.\...\\*
*........*
*....\.\.*
*\\......*
*....\.\.*
.\\....\.*
**********
-1 -1

[titid_gede]

i didnt see any better than DFS, but always TLE. what strategy can we use?

[titid_gede]

now i got WA in 0.7 Sec. i find that there will be many correct possible arrangement mirror for a maze. What we have to choose? What if we change the mirror that not lead to the exit?

[titid_gede]

I still havent found my mistakes. do you know where my mistake or can you give me a test that my program fail?
here is my code :
[c]
---cut----
[/c]

[titid_gede]

i have modified my algo, and i believe it should work, but still got WA. can you help me?

[c]
---cut got AC---
[/c]

[titid_gede]

what should be the output for maze that have no answer?

[titid_gede]

could it be possible there exist input like this?

Code: Select all

10 10 
**** ***** 
*..* *...* 
*/.. *...* 
*..* *...* 
*..***...* 
*/../....* 
*.**.*...* 
*.*  *...* 
*.*  *...* 
***  ***** 
-1 -1

[afonsocsc]

I don't think so, the exits must lead outside the maze...

[titid_gede]

i cant understand what you mean. so it means that the maze always rectangular? could it be a leading trailing spaces in the input? what kind of input is critical?

with love & light,

titid

[afonsocsc]

Yes, the maze is always rectangular with only two entry/exits, there are no leading spaces, all spaces are dots, I think there can be black holes inside the maze anywhere.

[epsilon0]

Dear broderic,

you are wrong about something (although it won't help you solve the problem):

you assume it is possible to encounter a mirror with its lock set to 2.
well it isn't. it is impossible to hit a mirror more than twice (once on each side).

think about it, and you'll see. it can be proved very easily.

it is also absolutely impossible to have a dead lock ( a cycle ).

the LASER beam enters, the LASER beam exits. plain and simple.

i am currently thinking about this problem, but haven't solved it yet. i am not satisfied with the DFS method and pondering something faster, but no much luck so far.

-----------------------------------------------------------
i discovered a few other things about this problem:
-----------------------------------------------------------

* some mirrors can be proved to be useless (ie the beam cannot go thru them and hit the exit or another mirror). such mirrors can be deleted, without consequences. see below for a method of finding them.

* in order to have a chance to be useful, a mirror needs to have at least one mirror in the same row AND one mirror in the same column. (the exit and the entrance are considered useful mirrors here)

* if a mirror has a chance to be useful, then it is possible to "lock" it if it only has mirrors above OR below (not both) AND mirrors on its left OR on its right (not both). (again exit and entrance are considered mirrors). then you can lock it and not bother again finding its position. you are not sure this mirror is useful, but in case it is, you already know the position it has.

* the problem with the above method is that some mirrors may stay ambiguous. then one can do a DFS.

* to get things faster, one can compute the path of the light beam on locked mirrors paths (those never changed since the mirrors are locked).

* since a mirror can be hit twice, one needs remember the position of mirrors when one does the DFS and take care of consistency.

this is all i can think of right now

one thing i tried was to reduce it to a graph problem, but it's not easy because of mirror mobility. it would be great though, much faster i think, once the graph is built.

best regards.

[epsilon0]

it is STATED in the problem description that all mazes admit at least one solution.
you could also notice that this problem has a special judge program. this is typical of problems that have several solutions. you can enter any solution, and the judge will check it.
it's different from other problems that dont have a special correcting program and expect a well defined output (correction is then merely a difference check between your output and a static file).

please read my post on the other thread about this problem and tell me what you think.

i have the same feeling as you about the DFS being inefficient, and somehow i first thought there was a faster way. i only have few hints to speed up the DFS process so far.

best regards.

[junbin]

I think your pruning would be useless for cases such as this:

Code: Select all

***********
.\/\/\/\/\*
*\/\/\/\/\.
***********

or

Code: Select all

***********
.\/\/\/\/\*
*\/\/\/\/.*
../\/\/\./*
***********

or simply expand the two even further.

[tomtung]

Hello, I'm new in uva. Mirror Maze is the first problem I tried to solve.
The code was compiled well on both WinXP(Dev-C++&g++) and ubuntu(Anjuta&g++), but I've got a CE after submittion. I didn't find the answer in "HOW TOs". What's wrong? Could you help me?

The code:

Code: Select all

code deleted after AC