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);
}
}