258 - Mirror Maze

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

Moderator: Board moderators

broderic
New poster
Posts: 34
Joined: Thu Jun 06, 2002 4:35 am
Location: Canada

258

Post by 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
New poster
Posts: 34
Joined: Mon Mar 24, 2003 1:15 am
Location: Portugal, Lisbon

Post by afonsocsc »

your program fails with this input:

Code: Select all

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

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

258 - Mirror Maze

Post by titid_gede »

i didnt see any better than DFS, but always TLE. what strategy can we use?
Last edited by titid_gede on Fri May 16, 2003 8:15 am, edited 1 time in total.
Kalo mau kaya, buat apa sekolah?

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by 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?
Kalo mau kaya, buat apa sekolah?

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by 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]
Kalo mau kaya, buat apa sekolah?

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

258 Mirror Maze WA

Post by 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]
Last edited by titid_gede on Wed May 21, 2003 7:50 am, edited 1 time in total.
Kalo mau kaya, buat apa sekolah?

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede »

what should be the output for maze that have no answer?
Kalo mau kaya, buat apa sekolah?

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede »

could it be possible there exist input like this?

Code: Select all

10 10 
**** ***** 
*..* *...* 
*/.. *...* 
*..* *...* 
*..***...* 
*/../....* 
*.**.*...* 
*.*  *...* 
*.*  *...* 
***  ***** 
-1 -1
Kalo mau kaya, buat apa sekolah?

afonsocsc
New poster
Posts: 34
Joined: Mon Mar 24, 2003 1:15 am
Location: Portugal, Lisbon

Post by afonsocsc »

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

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by 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
Kalo mau kaya, buat apa sekolah?

afonsocsc
New poster
Posts: 34
Joined: Mon Mar 24, 2003 1:15 am
Location: Portugal, Lisbon

Post by 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
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

wrong

Post by 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.
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

read more carefully

Post by 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.
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post by 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
New poster
Posts: 3
Joined: Wed Jun 06, 2007 7:18 am
Location: Lanzhou, Gansu, China
Contact:

Why CE???

Post by 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
Last edited by tomtung on Wed Jun 06, 2007 2:33 pm, edited 1 time in total.
And miles to go before I sleep,
and miles to go before I sleep...

Post Reply

Return to “Volume 2 (200-299)”