9期算法擂台源代码
骑士聚会在8×8的棋盘上分布着n个骑士,他们想约在某一格中聚会。骑士每天可以像国际象棋中的马那样移动一次,如图所示,可以从中间向8个方向移动,请你计算n个骑士的最早聚会地点和要走多少天。要求尽早聚会,且n个人走的总步数最少,先到聚会地点的骑士可以不再移动等待其他骑士。从键盘输入n(0 ),然后依次输入n个骑士的初始位置xi, yi(0 i, yi )。屏幕输出以空格分隔的三个整数,分
骑士聚会
在8×8的棋盘上分布着n个骑士,他们想约在某一格中聚会。骑士每天可以像国际象棋中的马那样移动一次,如图所示,可以从中间向8个方向移动,请你计算n个骑士的最早聚会地点和要走多少天。要求尽早聚会,且n个人走的总步数最少,先到聚会地点的骑士可以不再移动等待其他骑士。
从键盘输入n(0 < n <= 64),然后依次输入n个骑士的初始位置xi, yi(0 <= xi, yi <= 7)。屏幕输出以空格分隔的三个整数,分别为聚会点的x, y值,以及要走多少天?
#include <iostream>
#include <fstream>
#include <list>
using namespace std;
typedef int Board[8][8];
typedef pair<int, int> Pos;
void CalBoard(Board &bd, int x, int y);
void FindSpot(Board *pBoard, int n, int &x, int &y, int &day);
void AddPos(int x, int y, int day, Board &bd, list<Pos> &PosQue);
int main()
{
int n;
cin >> n;
Board *pBoards = new Board[n];
for (int i = 0; i < n; i++)
{
int x, y;
cin >> x >> y;
CalBoard(pBoards[i], x, y);
}
int x, y, day;
FindSpot(pBoards, n, x, y, day);
cout << x << ' ' << y << ' ' << day << endl;
delete [] pBoards;
return 0;
}
void CalBoard(Board &bd, int x, int y)
{
for (int i = 0; i < 8; i++)
for (int j = 0; j < 8; j++)
bd[i][j] = -1;
bd[x][y] = 0;
list<Pos> PosQue;
PosQue.push_back(Pos(x, y));
while (!PosQue.empty())
{
int x = PosQue.front().first;
int y = PosQue.front().second;
PosQue.pop_front();
int day = bd[x][y] + 1;
AddPos(x + 2, y + 1, day, bd, PosQue);
AddPos(x + 2, y - 1, day, bd, PosQue);
AddPos(x + 1, y + 2, day, bd, PosQue);
AddPos(x + 1, y - 2, day, bd, PosQue);
AddPos(x - 2, y + 1, day, bd, PosQue);
AddPos(x - 2, y - 1, day, bd, PosQue);
AddPos(x - 1, y + 2, day, bd, PosQue);
AddPos(x - 1, y - 2, day, bd, PosQue);
}
}
void FindSpot(Board *pBoard, int n, int &x, int &y, int &day)
{
day = 64; // max day
for (int i = 0; i < 8; i++)
for (int j = 0; j < 8; j++)
{
int maxday = 0;
for (int k = 0; k < n; k++)
if (pBoard[k][i][j] > maxday)
maxday = pBoard[k][i][j];
if (maxday < day)
{
day = maxday;
x = i;
y = j;
}
}
}
void AddPos(int x, int y, int day, Board &bd, list<Pos> &PosQue)
{
if ((0 <= x && x < 8) && (0 <= y && y < 8) && bd[x][y] < 0)
{
bd[x][y] = day;
PosQue.push_back(Pos(x, y));
}
}
更多推荐
所有评论(0)