挑战程序竞赛系列（5）：2.1广度优先搜索
版权声明：本文为博主原创文章，未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434748
2.1广度优先搜索
详细代码可以fork下Github上leetcode项目，不定期更新。
练习题如下：
AOJ 0558: Cheese
翻译参考博文【AOJ 0558 Cheese 《挑战程序设计竞赛(第2版)》练习题答案】
在H * W的地图上有N个奶酪工厂，分别生产硬度为1-N的奶酪。有一只吃货老鼠准备从老鼠洞出发吃遍每一个工厂的奶酪。老鼠有一个体力值，初始时为1，每吃一个工厂的奶酪体力值增加1（每个工厂只能吃一次），且老鼠只能吃硬度不大于当前体力值的奶酪。 老鼠从当前格走到相邻的无障碍物的格（上下左右）需要时间1单位，有障碍物的格不能走。走到工厂上时即可吃到该工厂的奶酪，吃奶酪时间不计。问吃遍所有奶酪最少用时。 输入：第一行三个整数H(1 <= H <= 1000)、W(1 <= W <=1000)、N(1 <= N <= 9)，之后H行W列为地图， “.“为空地， ”X“为障碍物，”S“为老鼠洞， 1-N代表硬度为1-N的奶酪的工厂。
思路：
依次求出1…N的最短路径，单纯的累加即可。BFS遍历得始终注意遍历过的点不要再添加到队列中去，其他没什么，注意下queue.size()的小技巧，累加步数非常有用。代码如下：
public class SolutionDay18_A0558 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int H = in.nextInt();
int W = in.nextInt();
int N = in.nextInt();
char[][] map = new char[H][W];
for (int i = 0; i < H; i++) {
char[] ss = in.next().trim().toCharArray();
for (int j = 0; j < W; j++) {
map[i][j] = ss[j];
}
}
System.out.println(solve(map,N));
in.close();
}
public static int solve(char[][] map, int N){
int row = map.length;
int col = map[0].length;
int[][] factory = new int[N+1][2];
for (int i = 0; i < row; i++){
for (int j = 0; j <col; j++){
if (map[i][j] == 'S'){
factory[0][0] = i;
factory[0][1] = j;
}
else if (map[i][j] != '.' && map[i][j] != 'X'){
factory[map[i][j]-'0'][0] = i;
factory[map[i][j]-'0'][1] = j;
}
}
}
int step = 0;
for (int i = 0; i < N; i++){
step += bfs(map, factory[i][0], factory[i][1], factory[i+1][0], factory[i+1][1]);
}
return step;
}
static int[][] dir = {{-1,0},{1,0},{0,-1},{0,1}};
private static int bfs(char[][] map, int sx, int sy, int ex, int ey){
int row = map.length, col = map[0].length;
int[][] distance = new int[row][col];
for (int i = 0; i < row; i++){
Arrays.fill(distance[i], -1);
}
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{sx, sy});
distance[sx][sy] = 0;
int step = 1;
while (!queue.isEmpty()){
int size = queue.size();
for (int i = 0; i < size; i++){
int[] cur = queue.poll();
for (int[] d : dir){
int nx = cur[0] + d[0];
int ny = cur[1] + d[1];
if (nx >= 0 && nx < row && ny >= 0 && ny < col && map[nx][ny] != 'X' && distance[nx][ny] == -1){
distance[nx][ny] = step;
queue.offer(new int[]{nx,ny});
}
}
}
step++;
}
return distance[ex][ey];
}
}POJ 3669: Meteor Shower
有个小文青去看流星雨，不料流星掉下来会砸毁上下左右中五个点。每个流星掉下的位置和时间都不同，求小文青能否活命，如果能活命，最短的逃跑时间是多少？
思路：
把流行能击中的区域全部求出来，用最小达到的时刻记录下来，这样留给小文青的逃跑路线是最紧张的。而未被击中的地方可以用INF表示这些区域相当安全。所以如果小文青能够跑到一个INF的地方，那么这就意味着他安全了。代码如下：
public class SolutionDay18_P3669 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int M = in.nextInt();
int[][] map = new int[M][2];
int[] T = new int[M];
for (int i = 0; i < M; i++){
map[i][0] = in.nextInt();
map[i][1] = in.nextInt();
T[i] = in.nextInt();
}
System.out.println(solve(map, T));
in.close();
}
static int[][] dir = {{-1,0},{1,0},{0,-1},{0,1},{0,0}};
static final int INF = 1 << 30;
private static int solve(int[][] map, int[] T){
int[][] distance = new int[512][512];
int[][] hit = new int[512][512];
for (int i = 0; i < distance.length; i++){
Arrays.fill(distance[i], INF);
Arrays.fill(hit[i], INF);
}
distance[0][0] = 0;
int M = map.length;
int last = T[0];
for (int i = 0; i < M; i++){
int x = map[i][0];
int y = map[i][1];
last = Math.max(last, T[i]);
for (int[] d : dir){
int nx = x + d[0];
int ny = y + d[1];
if (nx >= 0 && nx < 512 && ny >= 0 && ny < 512){
hit[nx][ny] = Math.min(hit[nx][ny], T[i]);
}
}
}
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{0,0});
if (hit[0][0] == 0) return -1;
int step = 0;
while (!queue.isEmpty()){
int size = queue.size();
step++;
for (int i = 0; i < size; i++){
int[] cur = queue.poll();
for (int k = 0; k < 4; k++){
int nx = cur[0] + dir[k][0];
int ny = cur[1] + dir[k][1];
if (nx >= 0 && nx < 512 && ny >= 0 && ny < 512 && step < hit[nx][ny] && distance[nx][ny] == INF){
distance[nx][ny] = step;
//关键，表示安全了，返回当前步数即可
if(hit[nx][ny] > last){
return step;
}
queue.offer(new int[]{nx,ny});
}
}
}
}
return -1;
}
}注意：step < hit[nx][ny]说明当step == hit[nx][ny]，恰巧被砸中，所以不会被放入队列中作为候选路径。
AOJ 0121: Seven Puzzle
题目大意可参考博文【AOJ 0558 Cheese 《挑战程序设计竞赛(第2版)》练习题答案】
思路：
该题的特点在于4*2的方框固定，所以我们完全可以构造解空间，而采用的手段是BFS，如何构造解空间，从初始数组”01234567”开始，寻找0的位置，让它与相邻位置交换，第二步继续寻找0的位置与相邻位置交换。而我们知道，在大量的交换过程中，会存在大量的重复解，遇到重复解，我们直接丢弃即可。所以队列是一个慢慢增大又慢慢减小的过程。
代码如下：
public class SolutionDay18_A0121 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
Map<String,Integer> map = bfs();
while(in.hasNext()){
String key = "";
for (int i = 0; i < 2; i++){
for (int j = 0; j < 4; j++){
key += in.nextInt();
}
}
System.out.println(map.get(key));
}
in.close();
}
static int[][] dir = {{-1,0},{1,0},{0,-1},{0,1}};
private static Map<String, Integer> bfs(){
Map<String, Integer> map = new HashMap<>();
map.put("01234567", 0);
char[][] init = {{'0','1','2','3'},{'4','5','6','7'}};
Queue<char[][]> queue = new LinkedList<>();
queue.offer(init);
while (!queue.isEmpty()){
char[][] now = queue.poll();
String nows = "";
int[] cur = new int[2];
for (int i = 0; i < 2; i++){
for (int j = 0; j < 4; j++){
nows += now[i][j]-'0';
if (now[i][j] == '0'){
cur[0] = i;
cur[1] = j;
}
}
}
for (int[] d : dir){
int nx = cur[0] + d[0];
int ny = cur[1] + d[1];
if (nx >= 0 && nx < 2 && ny >= 0 && ny < 4){
char[][] next = clone(now);
swap(next, cur[0], cur[1], nx, ny);
char[] ss = new char[8];
for (int i = 0, k = 0; i < 2; i++){
for (int j = 0; j < 4; j++){
ss[k++] = next[i][j];
}
}
String nn = new String(ss);
if (!map.containsKey(nn)){
map.put(nn, map.get(nows)+1);
queue.offer(next);
}
}
}
}
return map;
}
private static char[][] clone(char[][] now){
int row = now.length;
int col = now[0].length;
char[][] clone = new char[row][col];
for (int i = 0; i < row; i++){
for (int j = 0; j < col; j++){
clone[i][j] = now[i][j];
}
}
return clone;
}
private static void swap(char[][] map, int x1, int y1, int x2, int y2){
char tmp = map[x1][y1];
map[x1][y1] = map[x2][y2];
map[x2][y2] = tmp;
}
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2017年05月18日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
