一、问题描述
有一个 n * n 的矩阵,其中有四个2代表研究院,矩阵中 0 表示道路,1 表示不能走,只可以四个方向走,求找到一点(0点)距离四个研究院中最远的研究院的距离最近。
测试数据:
5
8 8
4
2 0 0 0 0 0 2 0
0 1 0 0 0 0 0 0
0 0 1 1 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0
0 1 1 1 1 1 0 0
0 2 0 0 0 0 0 2
3 3
2
0 1 1
2 1 0
0 0 2
4 4
3
2 0 1 1
0 0 0 0
0 0 1 0
1 2 0 2
10 10
4
0 0 1 0 2 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0
2 0 0 0 1 0 1 0 0 1
0 0 0 0 0 0 0 0 0 0
1 0 0 1 0 1 0 0 1 0
0 1 0 0 1 0 2 0 1 0
0 0 0 0 0 0 0 0 0 0
1 0 0 1 0 0 1 0 0 1
0 1 0 0 0 0 0 0 0 0
1 2 0 0 0 0 0 0 0 0
20 20
4
2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 2
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0
1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0
1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
二、DFS 版本,必定超时
1.思路:
(1)遍历所有的 0 点,找到距离每一个2的最近距离,保存下来。
这里就比较坑了,必须一个2一个2的找,当找任意一个2时,将其他的2设为0,因为2也可以走。这样相当于每一个0就要单纯的找4个2的最近距离,这样做是比较慢的。
(2)每走一个0点,求出其最远距离max。
(3)比较所有的0点的最远距离max,即可求出最终答案。
2.代码
package com.samsung.minroads;
import java.io.*;
import java.util.*;
public class MinRoads {
static int totalRow, totalCol, totalNum, max, minLen;
static int[][] data;
static int[] steps;
static int[][] dir = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } }; // 右,下,左,上
static boolean isEnd;
static Kuang[] kuangList;
static int kuIn;
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(new File("src/minroads.txt"));
int exit = sc.nextInt();
while ((exit--) >= 0) {
totalRow = sc.nextInt();
totalCol = sc.nextInt();
totalNum = sc.nextInt();
// init
data = new int[totalRow][totalCol];
steps = new int[(totalNum + 1)];
kuangList = new Kuang[totalNum + 1];
isEnd = false;
max = 0;
minLen = 1000;
kuIn = 0;
for (int i = 0; i <= totalNum; i++) {
steps[i] = 1000;
}
for (int i = 0; i < totalRow; i++) {
for (int j = 0; j < totalCol; j++) {
data[i][j] = sc.nextInt();
if (data[i][j] == 2) {
Kuang ku = new Kuang();
ku.x = i;
ku.y = j;
kuangList[kuIn++] = ku;
}
}
}
for (int i = 0; i < totalRow; i++) {
for (int j = 0; j < totalCol; j++) {
if (data[i][j] == 0) {
// init
// System.out.println("i:" + i + ",j:" + j);
for (int x = 0; x <= totalNum; x++) {
steps[x] = 1000;
}
max = 0;
for (int curK = 0; curK < kuIn; curK++) {
bfs(i, j, 0, 1, curK);
}
for (int k = 0; k < kuIn; k++) {
max = steps[k] > max ? steps[k] : max;
//System.out.println(steps[k]);
}
// System.out.println("max:" + max);
minLen = max < minLen ? max : minLen;
}
}
}
System.out.println("minLen:" + minLen);
}
}
// 到一个点距离最近
static void bfs(int row, int col, int curVal, int step, int curK) {
// System.out.println(step);
if(step > minLen){ // 剪枝
return;
}
int newRow, newCol;
for (int i = 0; i < 4; i++) {
newRow = row + dir[i][0];
newCol = col + dir[i][1];
if (newRow >= 0 && newRow < totalRow && newCol >= 0
&& newCol < totalCol) {
if (data[newRow][newCol] == 0 || data[newRow][newCol] == 2) {
if (data[newRow][newCol] == 2
&& (newRow == kuangList[curK].x && newCol == kuangList[curK].y)) {
steps[curK] = step < steps[curK] ? step : steps[curK];
return;
}
curVal = data[newRow][newCol];
data[newRow][newCol] = 8; // 8 不能走
bfs(newRow, newCol, curVal, step + 1, curK);
data[newRow][newCol] = curVal;
}
}
}
}
static void print() {
for (int i = 0; i < totalRow; i++) {
for (int j = 0; j < totalCol; j++) {
System.out.print(data[i][j] + " ");
}
System.out.println();
}
System.out.println();
}
}
class Kuang {
int x;
int y;
}
三、BFS 版本
方法一:
1.思路:
(1)遍历所有的0点,记录每个元素被遍历的步数,所以点走完一个0点时就可以得到4个2分别的步数,比较这4个步数获取最远距离max即可。
(2)遍历完所有的0点,就可以获取到最终的答案。
2.代码
package com.samsung.minroads;
import java.io.File;
import java.util.Scanner;
public class MinRoads2 {
static int totalRow, totalCol, totalNum,max,minLen;
static int[][] data,newData;
static int[][] dir = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } }; // 右,下,左,上
static Stone[] queue = new Stone[500]; // 走过的点
static int start,end;
static Stone[] stoneList; // 研究中心
static int stIn;
public static void main(String[] args) throws Exception{
Scanner sc = new Scanner(new File("src/roads.txt"));
int exit = sc.nextInt();
while ((exit--) != 0) {
totalRow = sc.nextInt();
totalCol = sc.nextInt();
totalNum = sc.nextInt();
// init
data = new int[totalRow][totalCol];
newData = new int[totalRow][totalCol];
stoneList = new Stone[totalNum + 1];
stIn = 0;
max = 0;
minLen = 1000;
for (int i = 0; i < totalRow; i++) {
for (int j = 0; j < totalCol; j++) {
data[i][j] = sc.nextInt();
newData[i][j] = data[i][j];
if (data[i][j] == 2) {
Stone stone = new Stone();
stone.x = i;
stone.y = j;
stone.size = 1000; // 方便计算
stoneList[stIn++] = stone;
}
}
}
for (int i = 0; i < totalRow; i++) {
for (int j = 0; j < totalCol; j++) {
if(data[i][j] == 0){
//System.out.println("i" + i + ",j:" + j);
for(int x = 0;x < 500;x++){
queue[x] = null;
}
start = 0;
end = 1;
max = 0;
Stone startSt = new Stone();
startSt.x = i;
startSt.y = j;
startSt.size = 1;
queue[0] = startSt;
bfs(0,1);
for(int k = 0;k < totalNum;k++){
Stone st = stoneList[k];
if(null != st){
max = st.size > max ? st.size : max;
st.size = 1000;
}
}
minLen = max < minLen ? max : minLen;
for (int m = 0; m < totalRow; m++) {
for (int n = 0; n < totalCol; n++) {
data[m][n] = newData[m][n];
}
}
}
}
}
System.out.println("minLen:" + minLen);
}
}
static void bfs(int step,int curStep){
int newRow, newCol;
int temp = 0;
Stone sto = queue[start++];
if(null != sto){
temp = sto.size;
if(temp >= step){
step = step + 1;
}
for (int i = 0; i < 4; i++) {
newRow = sto.x + dir[i][0];
newCol = sto.y + dir[i][1];
if (newRow >= 0 && newRow < totalRow && newCol >= 0
&& newCol < totalCol) {
if(data[newRow][newCol] != 1){
for(int k = 0;k < stIn;k++){
Stone exiStone = stoneList[k];
if(newRow == exiStone.x && newCol == exiStone.y){
exiStone.size = step < exiStone.size ? step : exiStone.size;
stoneList[k] = exiStone;
}
}
Stone st = new Stone();
st.x = newRow;
st.y = newCol;
st.size = step;
queue[end++] = st;
data[newRow][newCol] = 1;
}
}
}
bfs(step,sto.size);
}
}
}
class Stone{
int x;
int y;
int size;
}
方法二
1.思路
从2开始遍历,记录每个2到所有0点的距离,也是采用bfs遍历。这样做可以少走很多重复的路,复杂度和时间度都相对不负责。