Re: 11352 - Crazy King
Posted: 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...
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);
}
someone help please