骑士聚会问题——广度优先搜索

先来看下题目：

    

骑士聚会问题

在N*N的棋盘上放m个马，问各自跳多少步才能在某处聚在一起，希望聚会时间越早越好，且总步数最少，每天只能跳一步。

 

先指定各个骑士的起始位置，然后按广度优先搜索的方法遍历棋盘，标上到达的天数。

如图：

从0，0开始跳，遍历整个棋盘。

 

根据题意，越早聚会越好，所以应该首先把每个骑士的遍历结果对都先标在棋盘上。

例如4个骑士的遍历结果

每个方格的4个数字分别表示某一个骑士的遍历结果。到了这只须求出每个方格中的最大数，这个数即为每个方格的聚会时间，求出所有方格的最小值，即聚会的最短时间，如果有多个最小值，则求出最小步数，即每个方格和的最小值。

 

以上是总的思路，以下是详细代码：

package com.cong.algorithm;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class KnightMeet {

    public static void main(String[] args) {
  ArrayList list = new ArrayList();
  Scanner in = new Scanner(System.in);
  System.out.print("please input the number of knight :");
  int n = in.nextInt();
  for (int i = 0; i < n; i++) {
      System.out.print("please input the number " + i + " 's position :");
      int pos_i = in.nextInt();
      int pos_j = in.nextInt();
      list.add(new Knight(new Position(pos_i, pos_j)));
  }
  int[][] days = new int[Knight.N][Knight.N];
  int[][] tot_days = new int[Knight.N][Knight.N];
  int[] min = new int[Knight.N * Knight.N];
  int[] pos_i = new int[Knight.N * Knight.N];
  int[] pos_j = new int[Knight.N * Knight.N];
  int index = 0;
  min[index] = 12345;
  for (int i = 0; i < Knight.N; i++)
      for (int j = 0; j < Knight.N; j++) {
    days[i][j] = 0;
    tot_days[i][j] = 0;
    for (int num = 0; num < list.size(); num++) {
        if (list.get(num).getChess(i, j) > days[i][j])
      days[i][j] = list.get(num).getChess(i, j);
        tot_days[i][j] += list.get(num).getChess(i, j);
    }
    if (days[i][j] < min[index]) {
        index = 0;
        min[index] = days[i][j];
        pos_i[index] = i;
        pos_j[index] = j;
    } else if (days[i][j] == min[index]) {
        min[++index] = days[i][j];
        pos_i[index] = i;
        pos_j[index] = j;
    }
      }
  int po = 0;
  while (min[0] == min[po]) {
      System.out.println("use the least days in " + min[po] + " at "
        + pos_i[po] + "," + pos_j[po] + "with "
        + tot_days[pos_i[po]][pos_j[po]] + " foots");
      po++;
  }
    }
}

class Knight {
    public static final int N = 8;
    private static final Position[] orient = { new Position(-1, -2),
      new Position(-2, -1), new Position(-2, 1), new Position(-1, 2),
      new Position(1, 2), new Position(2, 1), new Position(2, -1),
      new Position(1, -2) };
    private int[][] chess;
    private Queue queue = new LinkedList();

    public Knight(Position now) {
  chess = new int[N][N];
  for (int i = 0; i < N; i++)
      for (int j = 0; j < N; j++)
    chess[i][j] = -1;
  queue.add(now);
  traverseChess();
    }

    private void traverseChess() {
  Position p;
  while ((p = queue.poll()) != null) {
      chess[p.i][p.j] = p.level;
      for (int i = 0; i < 8; i++) {
    Position temp_p = new Position(p.i + orient[i].i, p.j
      + orient[i].j);
    if (temp_p.i >= 0 && temp_p.i < N && temp_p.j >= 0
      && temp_p.j < N && chess[temp_p.i][temp_p.j] == -1) {
        temp_p.level = p.level + 1;
        queue.add(temp_p);
    }
      }
  }
    }

    public int getChess(int i, int j) {
  return chess[i][j];
    }
}

class Position {
    public Position(int i, int j) {
  this.i = i;
  this.j = j;
    }

    public int level = 0;
    public int i;
    public int j;
}