## 11352 - Crazy King

Moderator: Board moderators

Mushfiqur Rahman
Learning poster
Posts: 56
Joined: Tue Jun 13, 2006 5:18 pm
Contact:

### 11352 - Crazy King

Can anyone help?.!
I'm getting WA

Heres my code.

Code: Select all

``````Removed after Accepted
``````
Last edited by Mushfiqur Rahman on Wed Nov 14, 2007 8:00 am, edited 3 times in total.

New poster
Posts: 31
Joined: Sun Feb 25, 2007 6:33 pm
Location: Tehran
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
Learning poster
Posts: 56
Joined: Tue Jun 13, 2006 5:18 pm
Contact:

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
Learning poster
Posts: 65
Joined: Fri Jul 13, 2007 3:17 pm
I used BFS to solve this problem but I get WA.
Does anyone have critical test case ?

sapnil
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:
Why i'm getting WR Plz Help me

->Here my code

Code: Select all

``````// Code remove After Acc
``````
Thanks
Keep posting
Sapnil
Last edited by sapnil on Thu Nov 22, 2007 2:04 pm, edited 1 time in total.
"Dream Is The Key To Success"

@@@ Jony @@@

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
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
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
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
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:
Many many thanks to rio and sclo
its really help me;

Thanks
Keep posting
sapnil
"Dream Is The Key To Success"

@@@ Jony @@@

kolpobilashi
Learning poster
Posts: 54
Joined: Mon Jan 02, 2006 3:06 am
Contact:
can anyone tell me wat is the maximum size of the board/forest??
can't figure out the reason for getting WA :-L
Sanjana

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
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
New poster
Posts: 13
Joined: Thu Jun 14, 2007 8:48 am

### Re: 11352 - Crazy King

i use BFS but WA.I/O needed.
An offer u can not refuse.

Ron
Learning poster
Posts: 55
Joined: Mon Jul 23, 2007 5:01 pm
Location: INDIA

### Re: 11352 - Crazy King

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

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

kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Contact:

### Re: 11352 - Crazy King

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.
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................

Ron
Learning poster
Posts: 55
Joined: Mon Jul 23, 2007 5:01 pm
Location: INDIA

### Re: 11352 - Crazy King

Now i got ac.
Thanks kbr_iut !

r2ro
New poster
Posts: 38
Joined: Thu Sep 25, 2008 9:26 am

### Re: 11352 - Crazy King

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