【算法设计实验二】分治法解决棋盘覆盖问题

 

java">import java.util.*;

public class Main {
	
	static int cnt=0;
	
	public static void main(String[] args)
	{
		Scanner sc=new Scanner(System.in);
		
		System.out.println("请输入棋盘边长大小!");
		int n=sc.nextInt();
		int[][] g=new int[n][n];
		System.out.println("请输入特殊方格坐标!");
		int sx=sc.nextInt(),sy=sc.nextInt();
        g[sx][sy]=-1;
		System.out.println("——————————————————————");
		System.out.println("初始棋盘如下:");
		printRes(g);
		
		chessBoard(g,0,0,sx,sy,n);
		
		System.out.println("——————————————————————");
		System.out.println("结果如下:");
		printRes(g);
	}
	
	/*
	 * tx 当前划分棋盘的最左上角方格的x坐标
	 * ty 当前划分棋盘的最左上角方格的y坐标
	 * sx 特殊方格x坐标
	 * sy 特殊方格y坐标
	 * size 棋盘大小
	 */
	public static void chessBoard(int[][] g,int tx,int ty,int sx,int sy,int size)
	{
		//棋盘为1×1时结束
		if(size==1) return;
		
		int curs=size/2; //划分棋盘
		int num=++cnt;  
		
		//左上角
		if(sx<tx+curs && sy<ty+curs) //如果特殊方块在左上角
			chessBoard(g,tx,ty,sx,sy,curs);
		else
		{
			g[tx+curs-1][ty+curs-1]=num; //如果特殊方格没在,则将靠近中心的方块标记
			chessBoard(g,tx,ty,tx+curs-1,ty+curs-1,curs); //并将标记方块作为特殊方块进行棋盘划分
		}
		
		//右上角
		if(sx<tx+curs && sy>=ty+curs) //如果特殊方块在右上角
			chessBoard(g,tx,ty+curs,sx,sy,curs);
		else
		{
			g[tx+curs-1][ty+curs]=num; //如果特殊方格没在,则将靠近中心的方块标记
			chessBoard(g,tx,ty+curs,tx+curs-1,ty+curs,curs); //并将标记方块作为特殊方块进行棋盘划分
		}
		
		//左下角
		if(sx>=tx+curs && sy<ty+curs) //如果特殊方块在左下角
			chessBoard(g,tx+curs,ty,sx,sy,curs);
		else
		{
			g[tx+curs][ty+curs-1]=num; //如果特殊方格没在,则将靠近中心的方块标记
			chessBoard(g,tx+curs,ty,tx+curs,ty+curs-1,curs); //并将标记方块作为特殊方块进行棋盘划分
		}
		
		//右下角
		if(sx>=tx+curs && sy>=ty+curs) //如果特殊方块在右下角
			chessBoard(g,tx+curs,ty+curs,sx,sy,curs);
		else
		{
			g[tx+curs][ty+curs]=num; //如果特殊方格没在,则将靠近中心的方块标记
			chessBoard(g,tx+curs,ty+curs,tx+curs,ty+curs,curs); //并将标记方块作为特殊方块进行棋盘划分
		}
				
	}
	
	public static void printRes(int[][] g)
	{
		for(int[] x:g)
		{
			for(int i:x)
				System.out.print(i+" ");
			System.out.println();
		}
	}
	

}

 


http://www.niftyadmin.cn/n/5159313.html

相关文章

错误,LNK1107,文件无效或损坏

错误内容&#xff1a; LNK1107&#xff0c;文件无效或损坏&#xff1a;无法在0x406A4处读取 xxxx..\x64\Debug\xxx.obj 1 解决方案&#xff1a; 删除错误内容中提到的obj文件

【大厂招聘试题】__嵌入式开发工程师_2023届“联想”_1

目录 匹配职位&#xff1a;嵌入式开发工程师 1.&#xff08;单选题&#xff09;嵌入式系统按是否拥有通用操作系统来进行分类&#xff0c;可分为两种&#xff0c;分别为单片机和单板机&#xff0c;下列选项中属于单板机的是&#xff08; &#xff09; 2.&#xff08;单选题&…

从JDK8升级到JDK17

JDK8太老了&#xff0c;发布10年了吧&#xff0c;新开发的还是用最新免费长期支持版JDK17吧。这次把工程和环境升级到JDK17再继续后面工作&#xff0c;避免后面写多了还得解决升级问题。 先从官网下载JDK17 下载地址 解压后的文件夹放到一个位置 然后修改环境变量 修改好之…

PicoLog软件应用-电动车能耗记录

在这篇案例中&#xff0c;将为你分享PicoLog软件的应用&#xff0c;除此之外&#xff0c;你也会看到它与Picoscope 7软件的不同。 例如&#xff0c;客户在夜间给他/她的电动汽车&#xff08;EV&#xff09;充电&#xff0c;并由能源公司收取相应的电费。 电源消耗的计算公式如下…

调用DeleteLocalRef的正确姿势

做安卓jni相关开发的总会在涉及到jni变量释放时怀疑人生&#xff0c;what? where? when? who? why? how? how much? 最近碰到一个比较奇怪的问题&#xff0c;有一个jni方法的耗时在随着调用次数的增加而上涨&#xff0c;但是没有明显的内存泄漏&#xff0c;经过我缜密分…

阿里云oss迁移到AWS S3

这里写自定义目录标题 0.项目背景1.rclone 方式2.rsync方式3.注意 0.项目背景 公司迁移要求&#xff1a;从阿里云oss到亚马逊s3&#xff0c;数据量大概500G-2T左右。 开启阿里云oss 加速模式&#xff0c;这样能够跨机房和区域加速。 主要采用以下两种方式同步数据&#xff0c;…

重定向/请求转发

重定向: 重定向有几种方式&#xff1a; 1.通过response对象 2.在返回的字符串中加上redirect&#xff1a;表示重定向请求 比如&#xff1a; public String page(){return "index"; } public String redirect(){return "redirect:/index"; } page方法返…

怎么在相册里去水印?三种方法教你去除

当你查看相册时&#xff0c;有时可能会注意到一些照片上有水印&#xff0c;这可能会让人感到不满,不管你是想保存这些照片还是与他人分享&#xff0c;水印往往会影响图片的观赏效果&#xff0c;不过别担心我将向你介绍一些简单的方法&#xff0c;帮助你在相册中轻松去除这些水印…