# 2.1广度优先搜索

## AOJ 0558: Cheese

```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.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

```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.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;
}
}```

## AOJ 0121: Seven Puzzle

```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.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;
}

}```

0 条评论

• ### 算法原理系列：木桶排序

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### 挑战程序竞赛系列（36）：3.3线段树和平方分割

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### 挑战程序竞赛系列（21）：3.2反转

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### GO-回调函数

1，什么是回调函数。一个函数中有个参数为函数的指针。该函数自己调用自己指针函数即可； 2，为什么要使用回调函数。抽象画了一个函数，简洁代码。异步执行 3，例子：...

• ### C语言第七讲,函数入门.

C语言第七讲,函数入门. 一丶了解面向过程和面向对象的区别. 为什么要先讲面向过程和面向对象的区别? 面向过程,就是什么都要自己做.  比...

• ### 洛谷P1333 瑞瑞的木棍(欧拉回路)

题目描述 瑞瑞有一堆的玩具木棍，每根木棍的两端分别被染上了某种颜色，现在他突然有了一个想法，想要把这些木棍连在一起拼成一条线，并且使得木棍与木棍相接触的两端颜色...

• ### NYOJ 139 我排第几个(康拓展开+康拓展开逆运算)

康拓展开的裸题，对于康拓展开的定义是求当前的排列位于全排列中的第几个，比如132就是123的全排列的第二个，对于康拓展开的求法就是ans = ai...

• ### 蓝桥杯--算法入门级题目及答案解析

写在最前面： 本文中会出现大量的请查阅.请自学什么的，不是我不讲，本文是面向算法初学者和蓝桥杯的文章，如果真的想看进阶算法的也不会来看这些题目，所以不要介意，...

• ### 1001 舒适的路线 2006年

1001 舒适的路线 2006年 时间限制: 2 s 空间限制: 128000 KB 题目等级 : 钻石 Diamond 题目描述 Descrip...

• ### HDU 5677 ztr loves substring（回文串加多重背包）

ztr loves substring Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 655...