10967 - The Great Escape

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

Moderator: Board moderators

Post Reply
ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

10967 - The Great Escape

Post by ayon » 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...

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

Post by luishhh » Wed Dec 28, 2005 1:04 pm

It would be easier if you write or generate input, think about corner cases
"From lost to the river" --> Spanish quote

Post Reply

Return to “Volume 109 (10900-10999)”