第十一届蓝桥杯C组国赛B题-扩散-Java

题目：

题解：

DFS搜索速度过于缓慢，尝试BFS速度不错非常快。但是由于数组下表不可能有负数，因此，我们要先将这四个点坐标进行平移处理一下，保证在搜索过程中不会有负数的出现。

以源点(x,y)为中心，1分钟扩展一圈，那么2020分钟后上面点应该是(x,y+2020)，右边的点应该是(x+2020,y)，下边的点应该是(x,y-2020)，左边的点应该是(x-2020,y)。那么我们先观察一下这些源点能够扩散到的四个顶点是什么：

public static void main(String[] args) {
          
   
		int[][] p = {
          
   {
          
   0,0},{
          
   2020,11},{
          
   11,14},{
          
   2000,2000}};
		for(int i=0;i<4;i++) {
          
   
			System.out.printf("
(%d,%d):
",p[i][0],p[i][1]);
			System.out.printf("	上：(%d,%d)
",p[i][0],p[i][1]+2020);
			System.out.printf("	右：(%d,%d)
",p[i][0]+2020,p[i][1]);
			System.out.printf("	下：(%d,%d)
",p[i][0],p[i][1]-2020);
			System.out.printf("	左：(%d,%d)
",p[i][0]-2020,p[i][1]);
		}

运行结果：

(0,0):
	上：(0,2020)
	右：(2020,0)
	下：(0,-2020)
	左：(-2020,0)

(2020,11):
	上：(2020,2031)
	右：(4040,11)
	下：(2020,-2009)
	左：(0,11)

(11,14):
	上：(11,2034)
	右：(2031,14)
	下：(11,-2006)
	左：(-2009,14)

(2000,2000):
	上：(2000,4020)
	右：(4020,2000)
	下：(2000,-20)
	左：(-20,2000)

我们不难发现x坐标最小是-2020，y的最大坐标为4040。那么我们可以将数学中直角坐标系转换为数组的二维坐标系，我习惯的数组坐标是这样，请大家理解：

黑色为数学中直角坐标系，红色为数组中二维坐标系。

由于x最小为-2020，我们可以x向右平移3000，那么就不会出现负数了，也就是x+3000；

由于y最大为4040,我们可以让它转换为从上向下的y，可以用一个5000来转换他，也就是5000-y。

至此，我们完成了坐标转换，输出一下看看：

public static void main(String[] args) {
          
   
		int[][] p = {
          
   {
          
   0,0},{
          
   2020,11},{
          
   11,14},{
          
   2000,2000}};
		for(int i=0;i<4;i++) {
          
   
			System.out.printf("
(%d,%d):
",p[i][0],p[i][1]);
			System.out.printf("->(%d,%d)
",p[i][0]+3000,5000-p[i][1]);
		}
		
	}

运行结果：

(0,0):
->(3000,5000)

(2020,11):
->(5020,4989)

(11,14):
->(3011,4986)

(2000,2000):
->(5000,3000)

那么我们就开始多源BFS吧！让四个点同时开始扩散！！！

import java.util.LinkedList;
import java.util.Queue;

public class Main {
          
   
	// 记录是否到达过
	public static boolean[][] vis = new boolean[10000][10000];
	// 记录扩散点的个数
	public static int cnt;
	// 结点class
	public static class Node {
          
   
		int x,y,t;
		public Node() {
          
   }
		public Node(int x, int y, int t) {
          
   
			this.x = x;
			this.y = y;
			this.t = t;
		}
	}
	public static void main(String[] args) {
          
   
		int[][] p = {
          
   {
          
   0,0},{
          
   2020,11},{
          
   11,14},{
          
   2000,2000}};
		// 方向数组：上下左右
		int[][] dir = {
          
   {
          
   -1,0},{
          
   0,1},{
          
   1,0},{
          
   0,-1}};
		// 计数初始为4，因为有4个源点
		cnt = 4;
		
		Queue<Node> q = new LinkedList<Node>();
		// 将4个源点加入到队列中
		q.add(new Node(3000, 5000, 0));
		q.add(new Node(5020, 4989, 0));
		q.add(new Node(3011, 4986, 0));
		q.add(new Node(5000, 3000, 0));
		// 标记4个源点已访问
		vis[3000][5000] = true;vis[5020][4989] = true;
		vis[3011][4986] = true;vis[5000][3000] = true;
		
		// 开始BFS
		while(!q.isEmpty()) {
          
   
			Node head = q.poll();
			for(int i=0;i<4;i++) {
          
   
				// 遍历下一个可能的点
				Node next = new Node();
				next.x = head.x + dir[i][0];
				next.y = head.y + dir[i][1];
				next.t = head.t + 1;	// 距离加一
				// 判断是否没有走过 并且 距离小于2020
				if(!vis[next.x][next.y] && next.t <= 2020) {
          
   
					vis[next.x][next.y] = true;		// 标记走过
					cnt++;							// 计数器加一
					q.add(next);					// 加入队列
				}
			}
		}
		System.out.println(cnt);					// 完美输出
	}
}