第18章 广度优先搜索
2020-04-03 本文已影响0人
得力小泡泡
1、哆啦A梦的时光机
算法分析
题目讲述一共有4种移动情况且权重一致
- 从
X移动到X−1
- 从
X移动到X+1
-
从
X移动到2∗X -
若
X是偶数，从X移动到2∗X
相当于X 与X - 1,X + 1,2 * X ,各连一条边,从n开始进行bfs到k，dist[k]表示k点到n点的最短距离
时间复杂度 )
Java 代码
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
public class Main {
static int N = 1000010;
static int n;
static int k;
static int[] dist = new int[N];
static int bfs()
{
Queue<Integer> q = new LinkedList<Integer>();
Arrays.fill(dist, -1);
q.add(n);
dist[n] = 0;
while(!q.isEmpty())
{
int t = q.poll();
if(t - 1 >= 1 && dist[t - 1] == -1)
{
dist[t - 1] = dist[t] + 1;
if(t - 1 == k) return dist[t - 1];
q.add(t - 1);
}
if(t + 1 < N && dist[t + 1] == -1)
{
dist[t + 1] = dist[t] + 1;
if(t + 1 == k) return dist[t + 1];
q.add(t + 1);
}
if(t * 2 < N && dist[t * 2] == -1)
{
dist[t * 2] = dist[t] + 1;
if(t * 2 == k) return dist[t * 2];
q.add(t * 2);
}
if(t % 2 == 0 && t / 2 >= 1 && dist[t / 2] == -1)
{
dist[t / 2] = dist[t] + 1;
if(t / 2 == k) return dist[t / 2];
q.add(t / 2);
}
}
return -1;
}
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
int T = scan.nextInt();
while(T -- > 0)
{
n = scan.nextInt();
k = scan.nextInt();
System.out.println(bfs() * 2);
}
}
}
2、一维跳棋
算法分析
时间复杂度
Java 代码
3、蒜头君回家
算法分析
求出起始位置start到所有点的最短距离，再求出终点位置end到所有点的最短距离，跑两次bfs，枚举所有的P点，则从起点到P点再回到终点的距离为dist1[i][j] + dist2[i][j]，更新ans找到所有路径的最小值
时间复杂度 )
Java 代码
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static int N = 2010;
static int n,m;
static char[][] g = new char[N][N];
static Pair start,end;
static int ans = 0;
static int[][] dist1 = new int[N][N];//记录start到所有点的最短距离
static int[][] dist2 = new int[N][N];//记录end到所有点的最短距离
static int[] dx = new int[] {0,-1,0,1};
static int[] dy = new int[] {-1,0,1,0};
static void bfs(Pair start,int[][] dist)
{
for(int i = 0;i < n;i ++) Arrays.fill(dist[i], -1);
Queue<Pair> q = new LinkedList<Pair>();
dist[start.x][start.y] = 0;
q.add(start);
while(!q.isEmpty())
{
Pair t = q.poll();
for(int i = 0;i < 4;i ++)
{
int a = t.x + dx[i];
int b = t.y + dy[i];
if(a < 0 || a >= n || b < 0 || b >= m) continue;
if(dist[a][b] == -1 && g[a][b] != '#')
{
dist[a][b] = dist[t.x][t.y] + 1;
q.add(new Pair(a,b));
}
}
}
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
m = scan.nextInt();
for(int i = 0;i < n;i ++)
{
char[] temp = scan.next().toCharArray();
for(int j = 0;j < m;j ++)
{
g[i][j] = temp[j];
if(g[i][j] == 'S') start = new Pair(i,j);
if(g[i][j] == 'T') end = new Pair(i,j);
}
}
bfs(start,dist1);
bfs(end,dist2);
int ans = Integer.MAX_VALUE;
for(int i = 0;i < n;i ++)
for(int j = 0;j < m;j ++)
{
if(g[i][j] == 'P' && dist1[i][j] != -1 && dist2[i][j] != -1)
{
ans = Math.min(ans, dist1[i][j] + dist2[i][j]);
}
}
System.out.println(ans);
}
}
class Pair
{
int x,y;
Pair(int x,int y)
{
this.x = x;
this.y = y;
}
}
4、密码锁
算法分析
此题是求棋盘外的状态的最短路径问题，当前点到下面可以连上的点连上一个权值为1的边
- 1、将任何一位数字加
1 - 2、将任何一位数字减
1 - 3、交换相邻的数字
时间复杂度 线性复杂度
Java 代码
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static String start;
static String end;
static Map<String,Integer> dist = new HashMap<String,Integer>();
static String add(String s,int u)
{
String res = "";
for(int i = 0;i < 4;i ++)
{
if(i == u)
{
int x = s.charAt(u) - '0' + 1;
if(x == 10) x = 1;
res += x;
}
else res += s.charAt(i);
}
return res;
}
static String sub(String s,int u)
{
String res = "";
for(int i = 0;i < 4;i ++)
{
if(i == u)
{
int x = s.charAt(u) - '0' - 1;
if(x == 0) x = 9;
res += x;
}
else res += s.charAt(i);
}
return res;
}
static String swap(String s,int u)
{
char[] temp = s.toCharArray();
char t = temp[u];
temp[u] = temp[u + 1];
temp[u + 1] = t;
return String.valueOf(temp);
}
static int bfs()
{
Queue<String> q = new LinkedList<String>();
q.add(start);
dist.put(start, 0);
while(!q.isEmpty())
{
String t = q.poll();
//将任何一位数字加1
for(int i = 0;i < 4;i ++)
{
String s1 = add(t,i);
if(dist.containsKey(s1)) continue;
q.add(s1);
dist.put(s1, dist.get(t) + 1);
if(s1.equals(end)) return dist.get(end);
}
//将任何一位数字减1
for(int i = 0;i < 4;i ++)
{
String s2 = sub(t,i);
if(dist.containsKey(s2)) continue;
q.add(s2);
dist.put(s2, dist.get(t) + 1);
if(s2.equals(end)) return dist.get(end);
}
//交换相邻的数字
for(int i = 0;i < 3;i ++)
{
String s3 = swap(t,i);
if(dist.containsKey(s3)) continue;
q.add(s3);
dist.put(s3, dist.get(t) + 1);
if(s3.equals(end)) return dist.get(end);
}
}
return -1;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
start = scan.next();
end = scan.next();
System.out.println(bfs());
}
}
