骑士聚会

8×8的棋盘上分布着n个骑士,他们想约在某一格中聚会。骑士每天可以像国际象棋中的马那样移动一次,如图所示,可以从中间向8个方向移动,请你计算n个骑士的最早聚会地点和要走多少天。要求尽早聚会,且n个人走的总步数最少,先到聚会地点的骑士可以不再移动等待其他骑士。

从键盘输入n0 < n <= 64),然后依次输入n个骑士的初始位置xi, yi0 <= 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));
 }
}

 

Logo

20年前,《新程序员》创刊时,我们的心愿是全面关注程序员成长,中国将拥有新一代世界级的程序员。20年后的今天,我们有了新的使命:助力中国IT技术人成长,成就一亿技术人!

更多推荐