小蓝在一张无限大的特殊画布上作画。 这张画布可以看成一个方格图,每个格子可以用一个二维的整数坐标表示。 小蓝在画布上首先点了一下几个点:(0, 0), (2020, 11), (
小蓝在一张无限大的特殊画布上作画。
这张画布可以看成一个方格图,每个格子可以用一个二维的整数坐标表示。
小蓝在画布上首先点了一下几个点:(0, 0), (2020, 11), (11, 14), (2000, 2000)。
只有这几个格子上有黑色,其它位置都是白色的。
每过一分钟,黑色就会扩散一点。具体的,如果一个格子里面是黑色,它就会扩散到上、下、左、右四个相邻的格子中,使得这四个格子也变成黑色(如果原来就是黑色,则还是黑色)。
请问,经过 2020 分钟后,画布上有多少个格子是黑色的。
结果: 20312088
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
/**By CaesarChang张旭
*/public class Main {//设置行走方向 上下左右static int[][] direct= {{1,0},{0,-1},{0,1},{-1,0}};public static void main(String[] args) {// 初始化对象Location location1=new Location(3000, 3000);Location location2=new Location(5020, 3011);Location location3=new Location(3011, 3014);Location location4=new Location(5000, 5000);//获取一个队列Queue<Location> queue=new LinkedList<>();queue.add(location1);queue.add(location2);queue.add(location3);queue.add(location4);//记录是否走int visited[][]=new int[10010][10010];for(int i=0;i<visited.length;i++){Arrays.fill(visited[i],0);}int ans=0;//开始BFSint j=0;//来记录秒while(j<2020) {//当前秒队列里有多少点 nint n = queue.size();while(n-->0){//移除queue中的第一元素Location curLocation=queue.poll();visited[curLocation.x][curLocation.y]=1;//然后遍历这个位置的四周可以走通的位置,for(int i=0;i<direct.length;i++) {//如果这个位置的四个周围的节点是可以访问,那么假如队列里面int x=curLocation.x+direct[i][0];int y=curLocation.y+direct[i][1];if(visited[x][y]==1) {continue;}//满足条件 添加到队列里面//标记当前元素走过visited[x][y]=1;//扩散queue.add(new Location(x, y));}}j++;}for(int i=0;i<=10000;i++){for(int k=0;k<=10000;k++){if(visited[i][k]==1)ans++;}}System.out.println(ans);}}class Location{int x;int y;public Location(int x,int y) {this.x=x;this.y=y;}
}
发布者：admin，转转请注明出处：http://www.yc00.com/news/1700058305a969613.html
评论列表（0条）