11352 - Crazy King

[Mushfiqur Rahman]

Can anyone help?.!
I'm getting WA

Heres my code.

Code: Select all

Removed after Accepted

[saman_saadi]

The problem statement said that a horse can move atmost 1 movement so you shouldn't mark the squares that horse can reach with 'Z' if you do it then horse can move more than 1 movement so you must mark reachable squares by horse with another character and be careful about squares that there exist a horse in them!

[Mushfiqur Rahman]

Tahnks to Saman_saadi for your erly reply.

saman_saadi wrote:

The problem statement said that a horse can move atmost 1 movement so you shouldn't mark the squares that horse can reach with 'Z' if you do it then horse can move more than 1 movement so you must mark reachable squares by horse with another character and be careful about squares that there exist a horse in them!

But the problem statemen said

The problem statement said that a horse can move atmost 1 movement so you shouldn't mark the squares that horse can reach with 'Z' if you do it then horse can move more than 1 movement so you must mark reachable squares by horse with another character and be careful about squares that there exist a horse in them!

From statement its clear that a horse will disables 8 position if they r blank(.)

So I have to mark those position where a horse can reach by another symbol other than 'Z'. If I mark those position by 'Z' then it will be treat as a given horse( which is given in the input) and will make not reachable 8 new point for the king but this is not correct.

[RC's]

I used BFS to solve this problem but I get WA.
Does anyone have critical test case ?

[sapnil]

Why i'm getting WR Plz Help me

->Here my code

Code: Select all

// Code remove After Acc

Thanks
Keep posting
Sapnil

[rio]

In function void Black_invalid(long Row, long Col):

Code: Select all

            //Move 3; 
            ...
            r=i+2;
            c=i+1;      // !!
            ...

Writing the move one by one gets the code size large.
Heres a simple technique to reduce the code.

Code: Select all

// The Knight's move
   for (int e=-1; e<=1; e+=2)
      for (int f=-1; f<=1; f+=2) {
         r=i+e;
         c=j+2*f;
         if( (r>0&&r<=Row) && (c>0&&c<=Col) && Inp[r][c]=='.')
            {
               color[r][c]='b';
            }
         r=i+2*e;
         c=j+f;
         if( (r>0&&r<=Row) && (c>0&&c<=Col) && Inp[r][c]=='.')
            {
               color[r][c]='b';
            }
      }

// The King's move
   for (int i=-1; i<=1; ++i)
      for (int j=-1; j<=1; ++j)
         if (i || j) {
            r=y.x+i;c=y.y+j;
            Data.x=r;Data.y=c;
            if( (r>0&&r<=Row) && (c>0&&c<=Col) && color[r][c]=='w')
               {
                  color[r][c]='b';

                  Dist[r][c]=Dist[y.x][y.y]+1;
                  Enque(Data);
               }
         }

----
Rio

[sclo]

Here's another way to reduce even more code.
For the knight's move:

Code: Select all

int dx[] = {1,1,2,2,-1,-1,-2,-2};
int dy[] = {2,-2,1,-1,2,-2,1,-2};

for(k=0; k<8; k++) {
  r=i+dx[k], c=j+dy[k];
  if(inside(r,c) && Inp[r][c]=='.') color[r][c]='b';
} 

// inside(r,c) is true iff (r,c) is inside the board

[sapnil]

Many many thanks to rio and sclo
its really help me;

Thanks
Keep posting
sapnil

[kolpobilashi]

can anyone tell me wat is the maximum size of the board/forest??
can't figure out the reason for getting WA :-L

[sohel]

Lines from the problemstatement

Security Council of the King disposes information about location of the enemies, which makes the things easier for king. For some unknown reason a forest is M x N chessboard. (M is the number of rows, and N is the number of columns). N, M <= 100 are positive integers.

:-L

[sabir]

i use BFS but WA.I/O needed.

[Ron]

i also used bfs...and got WA....

Could anyone help us please .... !!!

[kbr_iut]

to Ron and Sabir.
try this case
input:

Code: Select all

1
5 5
....B
.....
.....
.Z...
A....

output:

Code: Select all

Minimal possible length of a trip is 5

hope it will help.if not post ur code.

[Ron]

Now i got ac.
Thanks kbr_iut !

[r2ro]

Anymore test cases? Still got WA as a verdict.

Here's my code if it helps

Code: Select all

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef char Grid[101][101];
typedef struct
{
        int x;
        int y;
        int value;
        int heur;
        int heurx;
        int heury;
} Node;

Node queue[10000];
Node visited[10000];

Grid grid;

int N,M,size,startx,starty,endx,endy,size2;

int abs(int n)
{
    if (n < 0)
       return 0-n;
    else
       return n;
}

bool isEmpty()
{
     if (size == 0)
        return true;
     else
         return false;
}

bool isValid2(int x,int y)
{
     if (x < N && x >= 0 && y < M && y >= 0)
     {
         if (grid[y][x] != 'Z' && grid[y][x] != 'W')  
           return true;
         else
           return false;
     }
     else
        return false;
}

bool contains(int x,int y)
{
     int i ;
     for (i = 0;i < size2;i++)
         if (x == visited[i].x && y == visited[i].y)
            return true;
     
     return false;
}

Node dequeue()
{
     Node v;
     int i,nTarg = 0;
     int nSmall = 9999,nSmallx = 9999,nSmally = 9999;
     for (i = 0;i < size;i++)
     {
         if (queue[i].heur < nSmall)
         {
              nSmall = queue[i].heur;
              nSmallx = queue[i].heurx;
              nSmally = queue[i].heury;
              nTarg = i;
         }
         else if (queue[i].heur == nSmall)
         {
              if (abs(queue[i].heurx-queue[i].heury) < abs(nSmallx-nSmally))
              {
                                                     nSmall = queue[i].heur;
                                                     nSmallx = queue[i].heurx;
                                                     nSmally = queue[i].heury;
                                                     nTarg = i;
              }
         }
     }
     v = queue[nTarg];
     for (i = nTarg;i < size-1;i++)
         queue[i] = queue[i+1];
     size--;
     return v;
}

void enqueue (Node q)
{
     queue[size] = q;
     visited[size2] = q;
     size++;
     size2++;
}

void refresh()
{
     size = 0;
     size2 = 0;
}

int get(int x,int y,int *uv,int *ue)
{
    int v;
    *uv = abs(endx-x);
    *ue = abs(endy-y);
    v = *uv + *ue;
    return v;
}

bool isValid(int y,int x)
{
     if (x < N && x >= 0 && y < M && y >= 0)
     {
         if (grid[y][x] == '.')
            return true;
     }
     return false;
}

bool bfs()
{
     bool bDone = false;
     Node temp,temp2;
     
     temp.x = startx;
     temp.y = starty;
     temp.value = 0;
     temp.heur = 0;
     temp.heurx = 0;
     temp.heury = 0;
     enqueue(temp);
     while (!isEmpty() && !bDone)
     {
           temp = dequeue();
   //        printf ("Exploring %d %d with value %d and heur %d\n",temp.x,temp.y,temp.value,temp.heur);
           if (temp.x == endx && temp.y == endy)
           {
              bDone = true;
              break;
           }
           if (isValid2(temp.x+1,temp.y) && contains(temp.x+1,temp.y) == false) // East
           {
                temp2.x = temp.x+1;
                temp2.y = temp.y;
                temp2.value = temp.value+1;
                temp2.heur = get(temp.x+1,temp.y,&temp2.heurx,&temp2.heury);
                enqueue(temp2);
           }
           if (isValid2(temp.x+1,temp.y+1) && contains(temp.x+1,temp.y+1) == false) // North Est
           {
                temp2.x = temp.x+1;
                temp2.y = temp.y+1;
                temp2.value = temp.value+1;
                temp2.heur = get(temp.x+1,temp.y+1,&temp2.heurx,&temp2.heury);
                enqueue(temp2);
           }
           if (isValid2(temp.x,temp.y+1) && contains(temp.x,temp.y+1) == false) // North
           {
                temp2.x = temp.x;
                temp2.y = temp.y+1;
                temp2.value = temp.value+1;
                temp2.heur = get(temp.x,temp.y+1,&temp2.heurx,&temp2.heury);
                enqueue(temp2);
           }
           if (isValid2(temp.x-1,temp.y+1) && contains(temp.x-1,temp.y+1) == false) // North West
           {
                temp2.x = temp.x-1;
                temp2.y = temp.y+1;
                temp2.value = temp.value+1;
                temp2.heur = get(temp.x-1,temp.y+1,&temp2.heurx,&temp2.heury);
                enqueue(temp2);
           }
           if (isValid2(temp.x-1,temp.y) && contains(temp.x-1,temp.y) == false) // West
           {
                temp2.x = temp.x-1;
                temp2.y = temp.y;
                temp2.value = temp.value+1;
                temp2.heur = get(temp.x-1,temp.y,&temp2.heurx,&temp2.heury);
                enqueue(temp2);
           }
           if (isValid2(temp.x-1,temp.y-1) && contains(temp.x-1,temp.y-1) == false) // South West
           {
                temp2.x = temp.x-1;
                temp2.y = temp.y-1;
                temp2.value = temp.value+1;
                temp2.heur = get(temp.x-1,temp.y-1,&temp2.heurx,&temp2.heury);
                enqueue(temp2);
           }
           if (isValid2(temp.x,temp.y-1) && contains(temp.x,temp.y-1) == false) // South
           {
                temp2.x = temp.x;
                temp2.y = temp.y-1;
                temp2.value = temp.value+1;
                temp2.heur = get(temp.x,temp.y-1,&temp2.heurx,&temp2.heury);
                enqueue(temp2);
           }
           if (isValid2(temp.x+1,temp.y-1) && contains(temp.x+1,temp.y-1) == false) // South East
           {
                temp2.x = temp.x+1;
                temp2.y = temp.y-1;
                temp2.value = temp.value+1;
                temp2.heur = get(temp.x+1,temp.y-1,&temp2.heurx,&temp2.heury);
                enqueue(temp2);
           }
     }
     
     if (!bDone)
        return false;
     else
         printf("Minimal possible length of a trip is %d\n",temp2.value);
     return true;
}

void flood()
{
     int i,j;
     for (i = 0;i < M;i++)
         for (j = 0;j < N;j++)
             if (grid[i][j] == 'Z')
             {
                  if (isValid(i-2,j-1))
                     grid[i-2][j-1] = 'W';
                  if (isValid(i-2,j+1))
                     grid[i-2][j+1] = 'W';
                  if (isValid(i-1,j-2))
                     grid[i-1][j-2] = 'W';
                  if (isValid(i+1,j-2))
                     grid[i+1][j-2] = 'W';
                  if (isValid(i+2,j-1))
                     grid[i+2][j-1] = 'W';
                  if (isValid(i+2,j+1))
                     grid[i+2][j+1] = 'W';
                  if (isValid(i-1,j+2))
                     grid[i-1][j+2] = 'W';
                  if (isValid(i+1,j+2))
                     grid[i+1][j+2] = 'W';
             }
}

int main()
{
    int testCase,i,j;
    char c;
    scanf("%d",&testCase);
    while (testCase--)
    {
          scanf("%d%c",&M,&c);
          scanf("%d%c",&N,&c);
          refresh();
          for (i = 0;i < M;i++)
              gets(grid[i]);
          flood();
          for (i = 0;i < M;i++)
              for (j = 0;j < N;j++)
                  if (grid[i][j] == 'A')
                  {
                                 startx = j;
                                 starty = i;
                  }
                  else if (grid[i][j] == 'B')
                  {
                                 endx = j;
                                 endy = i;
                  }
          if (!bfs())
             printf("King Peter, you can't go now!\n");
    }
}