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

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]);*

mazemaze

*[M+1]='*';*

}

for (i=1,sx=-1; i<=N; i+=N-1)

for (j=1; j<=M; j++) {

if (maze}

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=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]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]