## 10967 - The Great Escape

Moderator: Board moderators

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm

### 10967 - The Great Escape

hi, i got wa in this problem. will you give me some I/O that runs wrong in my code?
anyway here goes my code, the code is too long to read. if you just find any wrong output, please inform me. thanks in advance...

Code: Select all

``````#include <stdio.h>

struct rec1
{
char c;
int p;
int color;
int d;
} cell[101][101];

struct rec2
{
int x;
int y;
} Q[20500];

int m, n, time[505];

int abs(int a)
{
return a >= 0? a : -a;
}

int adjacent(int xx, int yy, int a, int b, int &dist)
{
int t, t1, t2;
dist = 1;
if(!(a >= 0 && a < m && b >=0 && b < n))
return 0;
if(cell[a][b].c == '#')
return 0;
else if(cell[xx][yy].c == '.')
{
if(cell[a][b].c == '.')
return 1;
else if(cell[a][b].c == 'W' && xx == a && yy == b-1)
return 1;
else if(cell[a][b].c == 'E' && xx == a && yy == b+1)
return 1;
else if(cell[a][b].c == 'N' && xx == a-1 && yy == b)
return 1;
else if(cell[a][b].c == 'S' && xx == a+1 && yy == b)
return 1;
else
return 0;
}
else
{
switch(cell[xx][yy].c)
{
case 'W':
t1 = 0;
break;
case 'N':
t1 = 1;
break;
case 'E':
t1 = 2;
break;
case 'S':
t1 = 3;
}
if(xx == a && yy == b+1)
t2 = 0;
else if(xx == a+1 && yy == b)
t2 = 1;
else if(xx == a && yy == b-1)
t2 = 2;
else if(xx == a-1 && yy == b)
t2 = 3;
if(cell[a][b].c != '.')
{
if(t2 == 0 && cell[a][b].c != 'E')
return 0;
if(t2 == 1 && cell[a][b].c != 'S')
return 0;
if(t2 == 2 && cell[a][b].c != 'W')
return 0;
if(t2 == 3 && cell[a][b].c != 'N')
return 0;
}
t = abs(t1-t2);
if(t == 3)
t = 1;
dist += time[cell[xx][yy].p]*t;
return 1;
}
}

void main()
{
static int white = 0, gray = 2;
int test, tc, i, j, k, r, f, xx, yy, a, b, dist;
char ch;
scanf("%d", &test);
for(tc = 0; tc < test; ++tc)
{
scanf("%d%d", &m, &n);
k = 0;
for(i = 0; i < m; ++i)
for(j = 0; j < n; ++j)
{
scanf(" %c", &ch);
if(ch != '.' && ch != '#')
cell[i][j].p = k++;
cell[i][j].c = ch;
cell[i][j].color = white;
cell[i][j].d = -1;
}
for(i = 0; i < k; ++i)
scanf("%d", &time[i]);
cell[m-1][0].color = gray;
cell[m-1][0].d = 0;
r = f = 0;
Q[++r].x = m-1;
Q[r].y = 0;
while(r > f)
{
xx = Q[++f].x;
yy = Q[f].y;
///////////////////////////////////////////////
a = xx-1;
b = yy;
{
if(cell[a][b].color == white)
{
cell[a][b].color = gray;
cell[a][b].d = cell[xx][yy].d + dist;
Q[++r].x = a;
Q[r].y = b;
}
else if(cell[a][b].color == gray)
{
if(cell[a][b].d > cell[xx][yy].d + dist)
{
cell[a][b].d = cell[xx][yy].d + dist;
Q[++r].x = a;
Q[r].y = b;
}
}
}
///////////////////////////////////////////////
a = xx;
b = yy-1;
{
if(cell[a][b].color == white)
{
cell[a][b].color = gray;
cell[a][b].d = cell[xx][yy].d + dist;
Q[++r].x = a;
Q[r].y = b;
}
else if(cell[a][b].color == gray)
{
if(cell[a][b].d > cell[xx][yy].d + dist)
{
cell[a][b].d = cell[xx][yy].d + dist;
Q[++r].x = a;
Q[r].y = b;
}
}
}
///////////////////////////////////////////////
a = xx;
b = yy+1;
{
if(cell[a][b].color == white)
{
cell[a][b].color = gray;
cell[a][b].d = cell[xx][yy].d + dist;
Q[++r].x = a;
Q[r].y = b;
}
else if(cell[a][b].color == gray)
{
if(cell[a][b].d > cell[xx][yy].d + dist)
{
cell[a][b].d = cell[xx][yy].d + dist;
Q[++r].x = a;
Q[r].y = b;
}
}
}
///////////////////////////////////////////////
a = xx+1;
b = yy;
{
if(cell[a][b].color == white)
{
cell[a][b].color = gray;
cell[a][b].d = cell[xx][yy].d + dist;
Q[++r].x = a;
Q[r].y = b;
}
else if(cell[a][b].color == gray)
{
if(cell[a][b].d > cell[xx][yy].d + dist)
{
cell[a][b].d = cell[xx][yy].d + dist;
Q[++r].x = a;
Q[r].y = b;
}
}
}
}
/*      for(i = 0; i < m; ++i)
{
for(j = 0; j < n; ++j)
printf("%d ", cell[i][j].d);
putchar('\n');
}					*/
if(cell[0][n-1].d == -1)
printf("Poor Kianoosh\n");
else
printf("%d\n", cell[0][n-1].d);
}
}
``````
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

luishhh
New poster
Posts: 26
Joined: Mon Oct 25, 2004 8:11 pm
Location: Spain
It would be easier if you write or generate input, think about corner cases
"From lost to the river" --> Spanish quote