11352 - Crazy King

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

Moderator: Board moderators

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

Re: 11352 - Crazy King

Post by StAnger » Thu Sep 17, 2009 10:45 pm

And is there any more special cases in dealing with this?
I've read the thread above but still can't get AC.
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
Location: University Of Dhaka,Bangladesh
Contact:

Re: 11352 - Crazy King

Post by Shafaet_du » Fri Sep 10, 2010 8:32 pm

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

Post by live_lie » Mon Jun 13, 2011 6:27 pm

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

Post by live_lie » Sat Jun 25, 2011 7:52 pm

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

Post by Scarecrow » Wed Jul 18, 2012 1:30 am

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

Post by Faithkeeper_Rangwan » Sat Aug 10, 2013 12:39 pm

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':
					{
						addHorse(i,j,m,n);
					}
				}
			}
			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

Post by brianfry713 » Wed Aug 14, 2013 10:49 pm

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: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

Re:

Post by Mukit Chowdhury » Sun Sep 15, 2013 9:46 pm

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... :D

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

Re: 11352 - Crazy King

Post by brianfry713 » Mon Sep 16, 2013 7:57 pm

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: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

Re: 11352 - Crazy King

Post by Mukit Chowdhury » Mon Sep 16, 2013 8:17 pm

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

Post by brianfry713 » Mon Sep 16, 2013 11:16 pm

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: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

Re: 11352 - Crazy King

Post by Mukit Chowdhury » Tue Sep 17, 2013 9:28 am

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

Post by brianfry713 » Tue Sep 17, 2013 9:48 pm

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

Post by jalil_cse » Wed Jan 29, 2014 7:52 pm

why wa please help me........

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

Post by brianfry713 » Wed Jan 29, 2014 11:21 pm

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!

Post Reply

Return to “Volume 113 (11300-11399)”