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