10967 - The Great Escape
Posted: Wed Dec 28, 2005 10:39 am
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...
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(adjacent(xx, yy, a, b, dist))
{
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(adjacent(xx, yy, a, b, dist))
{
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(adjacent(xx, yy, a, b, dist))
{
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(adjacent(xx, yy, a, b, dist))
{
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);
}
}