11352 - Crazy King

Moderator: Board moderators

StAnger
New poster
Posts: 3
Joined: Tue Sep 08, 2009 11:15 pm

Re: 11352 - Crazy King

And is there any more special cases in dealing with this?
Can someone help me to find out where my problem is?
Thanks a lot...

Code: Select all

``````#include <iostream>
#include <queue>
#include <string>
using namespace std;

class PathRecord {
int x, y;
int length;
public:
PathRecord() {
x = 0; y = 0;
length = 0;
}
PathRecord(int l, int a, int b) {
x = a; y = b;
length = l;
}

int get_pos_x() const {
return x;
}
int get_pos_y() const {
return y;
}
int get_length() const {
return length;
}
};

bool operator<(const PathRecord &a, const PathRecord &b)
{
return a.get_length() >= b.get_length();
}

priority_queue<PathRecord> q;

void Map_input(int Map[][100], int M, int N, int *Ax, int *Ay) {
int j, k;
for(j=0; j<M; j++) {
for(k=0; k<N; k++) {
Map[j][k] = fgetc(stdin);
switch(Map[j][k]) {
case '.':
Map[j][k] = -1;
break;
case 'Z':
Map[j][k] = -2;
break;
case 'A':
Map[j][k] = 0;
*Ax = j; *Ay = k;
break;
case 'B':
Map[j][k] = -4;
break;
default:
k--;
}
}
}
}

void Map_output(int Map[][100], int M, int N) {
int j, k;
for(j=0; j<M; j++) {
for(k=0; k<N; k++) {
switch(Map[j][k]) {
case -1:
printf(". ");
break;
case -2:
printf("Z ");
break;
case -3:
printf("X ");
break;
case 0:
printf("A ");
break;
case -4:
printf("B ");
break;
default:
if(Map[j][k] > 9) printf("%d", Map[j][k]);
else printf("%d ", Map[j][k]);
}
}
printf("\n");
}
}

int Inmap(int x, int y, int M, int N) {
if(0<=x && x<M && 0<=y && y<N) return(1);
else return(0);
}

void Knight_move(int Map[][100], int M, int N) {
int i, j, k;
int x, y;
int dx[] = {1,1,2,2,-1,-1,-2,-2};
int dy[] = {2,-2,1,-1,2,-2,1,-1};

for(i=0; i<M; i++) {
for(j=0; j<N; j++) {
if(Map[i][j]==-2)
for(k=0; k<8; k++) {
x = i + dx[k]; y = j + dy[k];
if(Inmap(x, y, M, N) && Map[x][y]==-1) {
Map[x][y] = -3;
}
}
}
}
}

void Path_search(int Map[][100], int M, int N) {
int Bx, By, x, y, length = 0;
int pathfound = 0;
int i, j, k;
int dx[] = {1,1,1,0,0,-1,-1,-1};
int dy[] = {1,0,-1,1,-1,1,0,-1};

while(!q.empty() && pathfound==0) {
if(pathfound == 1) printf("5");
//Popqueue data
length= q.top().get_length();
i = q.top().get_pos_x();
j = q.top().get_pos_y();
//printf("(%d,%d):%d\n", i, j, length);
//system("pause");
for(k=0; k<8; k++) {
x = i + dx[k]; y = j + dy[k];
if(Inmap(x, y, M, N) && pathfound==0) {
switch(Map[x][y]) {
case -1: // '.'
Map[x][y] = length + 1;
//Enqueue(Map[x][y], x, y);
q.push(PathRecord(Map[x][y], x, y));
break;
case -2: // 'Z'
break;
case -3: // 'X'
break;
case -4: // 'B'
Map[x][y] = length + 1;
pathfound = 1;
Bx = x; By = y;
break;
case 0:  // 'A'
break;
default:
if(Map[x][y] > length + 1) {
Map[x][y] = length + 1;
//Enqueue(Map[x][y], x, y);
q.push(PathRecord(Map[x][y], x, y));
}
}
//dequeue();
}
if(pathfound == 1) k=8;
}
q.pop();
}
if(pathfound==0) printf("King Peter, you can't go now!\n");
else printf("Minimal possible length of a trip is %d\n", Map[Bx][By]);
}

int main()
{
int T, M, N;
int Map[100][100]; // 'A'=0, '.'=-1, 'Z'=-2, 'X'=-3, 'B'=-4
int Ax, Ay;
int i, j, k;

scanf("%d", &T);

for(i=0; i<T; i++) {
scanf("%d", &M);
scanf("%d", &N);
Map_input(Map, M, N, &Ax, &Ay);
Knight_move(Map, M, N);
q.push(PathRecord(0, Ax, Ay));
Path_search(Map, M, N);
//Map_output(Map, M, N);
}

return(0);
}
``````

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Contact:

Re: 11352 - Crazy King

If you can pass these,you should get AC:

Code: Select all

``````6
5 5
Z....
....B
.....
.....
A...Z
8 8
Z.......
....B...
........
........
....Z...
.Z......
........
A......Z
8 9
Z.......Z
....B....
....Z....
...Z.....
....Z....
.Z....Z..
.........
.....A.Z.
8 9
Z.......Z
..Z.B..Z.
....Z....
...Z.....
....Z....
.Z....Z..
.........
.....A.Z.
1 2
AB
3 3
B..
..Z
A..
``````
output:

Code: Select all

``````Minimal possible length of a trip is 4
Minimal possible length of a trip is 7
Minimal possible length of a trip is 9
King Peter, you can't go now!
Minimal possible length of a trip is 1
Minimal possible length of a trip is 2
``````

live_lie
New poster
Posts: 19
Joined: Mon Nov 29, 2010 11:50 pm

Re: 11352 - Crazy King

my code give the same output for above input but still wrong answer...plz help

live_lie
New poster
Posts: 19
Joined: Mon Nov 29, 2010 11:50 pm

Re: 11352 - Crazy King

AC. there was a problem of just one "=" thats why i get a huge pain.

Scarecrow
Learning poster
Posts: 69
Joined: Wed Oct 19, 2011 9:06 pm

Re: 11352 - Crazy King

my program passes all the I/O of this board, and can't find any critical/tricky I/O. getting WA someone help please

Code: Select all

``````AC
``````
Do or do not. There is no try.

Faithkeeper_Rangwan
New poster
Posts: 12
Joined: Sun Jul 07, 2013 7:32 pm

Re: 11352 - Crazy King

The whole thing seems correct, but still got WA

Code: Select all

``````#include <iostream>
#include <queue>
#include <cstring>
#include <string>
long mp[100][100];
std::pair<int,int> horseMove[8] = {std::make_pair(1,2),std::make_pair(2,1),std::make_pair(-1,2),std::make_pair(-2,1),std::make_pair(1,-2),std::make_pair(2,-1),std::make_pair(-1,-2),std::make_pair(-2,-1)};
std::pair<int,int> kingMove[8]  = {std::make_pair(1,1),std::make_pair(-1,1),std::make_pair(1,-1),std::make_pair(-1,-1),std::make_pair(0,1),std::make_pair(1,0),std::make_pair(0,-1),std::make_pair(-1,0)};
void addHorse(int x, int y,int sx, int sy)
{
mp[x][y] = -2;
for(int i = 0; i<8; i++)
{
int ai = x+horseMove[i].first,aj = y+horseMove[i].second;
if((ai>=0)&&(ai<sx)&&(aj>=0)&&(aj<sy)) if(mp[ai][aj]) mp[ai][aj] = -2;
}
}
int main()
{
int tc,m,n;
std::cin>>tc;
std::pair<int,int> startP,endP;
std::string txt;
while(tc--)
{
memset(mp,-1,sizeof(long)*10000);
std::cin>>m>>n;
for(int i = 0; i<m; i++)
{
std::cin>>txt;
for(int j = 0; j<n; j++)
{
switch (txt[j])
{
case 'A':
{
startP = std::make_pair(i,j);
mp[i][j] = 0;
break;
}
case 'B':
{
endP = std::make_pair(i,j);
mp[i][j] = 0;
break;
}
case 'Z':
{
}
}
}
mp[startP.first][startP.second] = 0;
mp[endP.first][endP.second] = -1;
}
std::queue<std::pair<int,int> > kill;
kill.push(startP);
while(!kill.empty())
{
std::pair<int,int> tq = kill.front();
kill.pop();
//if(tq==endP) break;
for(int i = 0; i<8; i++)
{
int ai = tq.first+kingMove[i].first,aj = tq.second+kingMove[i].second;
if((ai>=0)&&(ai<m)&&(aj>=0)&&(aj<n)&&(mp[ai][aj]!=-2)&&(mp[ai][aj]==-1||mp[ai][aj]>(mp[tq.first][tq.second]+1))) {mp[ai][aj] = mp[tq.first][tq.second]+1;kill.push(std::make_pair(ai,aj));}
}
}
if(mp[endP.first][endP.second]<0)
{
std::cout<<"King Peter, you can't go now!"<<std::endl;
}
else
{
std::cout<<"Minimal possible length of a trip is "<<mp[endP.first][endP.second]<<std::endl;
}
}
return 0;
}``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11352 - Crazy King

Move lines 52 and 53:

Code: Select all

``````             mp[startP.first][startP.second] = 0;
mp[endP.first][endP.second] = -1;``````
after line 54:

Code: Select all

``          }``
Check input and AC output for thousands of problems on uDebug!

Mukit Chowdhury
Learning poster
Posts: 99
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

Re:

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 where it's said that, a horse can move at most 1 movement ??? After visiting in discuss board I make me known about it. May be I'm missing something, Would anybody please tell me, which line of problem statement indicates about 1 movement of the horse's movement ???

*** Anyway, my code is accepted...

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11352 - Crazy King

if at least one horse can reach square X in one move, then king can't move to that square
Check input and AC output for thousands of problems on uDebug!

Mukit Chowdhury
Learning poster
Posts: 99
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

Re: 11352 - Crazy King

Lets consider a case:
A 5*5 chessboard.
.B...
.....
.....
.A...
...ZZ

Output for this input is 3. ((3,2)>(2,2)>(1,2))
Here, the horse staying in (5,5) (1 based indexing), can go to (3,4). and the king can go to (3,2). Now current position of king is (3,2) and current position of the horse is
(3,4). Now how the king go to (2,2) where from (3,4) the horse can go to (2,2) in one move ???
My confusion is here... Please remove my confusion....

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11352 - Crazy King

I marked the points that can be attacked by a horse in one move with *

Code: Select all

``````.B...
.....
..***
.A*..
...ZZ``````
Check input and AC output for thousands of problems on uDebug!

Mukit Chowdhury
Learning poster
Posts: 99
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

Re: 11352 - Crazy King

It's my fault... I am failed to express my problem...
OK, I'm trying again... please give a look again...
Initially the chessboard looks like,

Code: Select all

``````.B...
.....
..***
.A*..
...ZZ``````
suppose, horse of square(5,5) has gone to (3,4), and horse of square(5,4) has gone to (3,3). And the king has gone to (3,2).
Then the chessboard looks like,

Code: Select all

``````.B...
**...
.AZZ.
.....
.....``````
In this state, for the horse of square(3,4), the king shouldn't go to (2,2), as the horse of (3,4) can go to (2,2) in one move.
But in this problem, only first move of horse from initial position is considered. Why don't we consider the steps after first move ???

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11352 - Crazy King

While the king is moving horses are not, but if at least one horse can reach square X in one move, then king can't move to that square (except for the case when square X is either kingdom A or B).

In this problem you only have to consider where each horse can go in ONE move.
Check input and AC output for thousands of problems on uDebug!

jalil_cse
New poster
Posts: 8
Joined: Tue Dec 25, 2012 12:35 pm

Re: 11352 - Crazy King

Code: Select all

``````thank you brianfry713
``````
Last edited by jalil_cse on Thu Jan 30, 2014 7:55 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11352 - Crazy King

Changes lines 12 and 13 to:
int rx[]={-1,0,1, 0,-1,-1,1, 1};
int ry[]={ 0,1,0,-1,-1, 1,1,-1};
Check input and AC output for thousands of problems on uDebug!