chessplate.java

分治算法解决棋盘覆盖问题

import java.lang.*;
import java.io.*;
import java.util.*;
class mi
	{  int micheng(int q)        //幂方法计算2的k次方的值
		{	int k=1;
	        for(int i=0;i<q;i++)
	       	k=2*k;
	        return k;
         }
	}
public class  chessplate
{    static int num;
	 int tile=1;
	 int Board[][]=new int [num][num];  		//二位数组定义存储棋盘的
	 void fugai(int x,int y,int line,int row,int size)
		{  int t=tile++;
	       int s=size/2;
	     if(size==1) 	return ;
		 if(line<=x+s-1&&row<=y+s-1)           //残缺方格位于第二象限
            fugai(x,y,line,row,s);             //在本象限内调用递归程序
	     else                                  //本象限中没有残缺方格
           {
              Board[x+s-2][y+s-2]=t;           //将小方格板t放在此象限右下角
              fugai(x,y,x+s-1,y+s-1,s);     
	       }
         if(line<=x+s-1&&row>=y+s)             //残缺方格位于第一象限
              fugai(x,y+s,line,row,s);
         else                                  //本象限中没有残缺方格
           {
               Board[x+s-2][y+s-1]=t;          //将小方格板t放在此象限左下角
	           fugai(x,y+s,x+s-1,y+s,s);       
             }
          if(line>=x+s&&row<=y+s-1)            //残缺方格位位于第三象限
              fugai(x+s,y,line,row,s);
          else
            {
                Board[x+s-1][y+s-2]=t;         //将小方格板t放在此象限右上角
               fugai(x+s,y,x+s,y+s-1,s);      
            }
          if(line>=x+s&&row>=y+s)              //残缺方格位位于第四象限
                fugai(x+s,y+s,line,row,s);
          else
            {
                 Board[x+s-1][y+s-1]=t;         //将小方格板t放在此象限左上角
                fugai(x+s,y+s,x+s,y+s,s);    
             }
		}
	  void shuchu()                            //此方法完成棋盘覆盖方案的输出
      {	
		
		 for(int i=0;i<num;i++)
          {
           for(int j=0;j<num;j++)
          System.out.print("   "+Board[i][j]);
		  System.out.println(); 
           }
	   }
	  int tongji1()
		{  int number1=0;
			for(int i=1;i<num;i++)
			{for(int j=0;j<num-1;j++)
				{ if(Board[i][j]==Board[i-1][j]&&Board[i][j]==Board[i][j+1])
					number1++;
			     }
			}
			return number1;
		}
	  int tongji2()
		{  int number2=0;
			for(int i=1;i<num;i++)
			{for(int j=1;j<num;j++)
				{ if(Board[i][j]==Board[i][j-1]&&Board[i][j]==Board[i-1][j])
					number2++;
			     }
			}
			return number2;
		}
	  int tongji3()
		{  int number3=0;
			for(int i=0;i<num-1;i++)
			{for(int j=0;j<num-1;j++)
				{ if(Board[i][j]==Board[i+1][j]&&Board[i][j]==Board[i][j+1])
					number3++;
				}
			 } 
			return number3;
		 }
	  int tongji4()
		  {  int number4=0;
			for(int i=0;i<num-1;i++)
			{for(int j=1;j<num;j++)
				{ if(Board[i][j]==Board[i+1][j]&&Board[i][j]==Board[i][j-1])
					number4++;
				}
			 }	
			return number4;
		 }
  public static void main(String args[])
		{ //chessplate pp=new chessplate();
		System.out.println("请输入棋盘的大小k值");
        BufferedReader cc;
        String aa;
		int number=0,result;
		mi kk=new mi();
        try{
	    	cc=new BufferedReader(new InputStreamReader(System.in));
	    	aa=cc.readLine();
	    	number=Integer.parseInt(aa);
		   }catch(IOException e){System.out.println(e);}
        result=kk.micheng(number);
		System.out.println("您输入的棋盘的大小为:"+result+"*"+result+"");
		System.out.println(); 
		num=result;
		chessplate pp=new chessplate();
	    Random x1=new Random();
	    int x=Math.abs(x1.nextInt())%result;
	    int y=Math.abs(x1.nextInt())%result;
	    System.out.println("随机产生的棋盘残缺方格在第"+x+"行"+"第"+y+"列");  
		System.out.println(); 
		pp.fugai(1,1,x,y,result); 
         pp.shuchu(); 
		System.out.println(); 
		int num1=pp.tongji1();
		int num2=pp.tongji2();
		int num3=pp.tongji3();
		int num4=pp.tongji4();
		System.out.println("填充棋盘共用┗型三格板"+num1+"块");
		System.out.println(); 
	    System.out.println("填充棋盘共用┛型三格板"+num2+"块");
		System.out.println(); 
		System.out.println("填充棋盘共用┏型三格板"+num3+"块");
		System.out.println();  
		System.out.println("填充棋盘共用┓型三格板"+num4+"块");
		System.out.println(); 
		System.out.println("填充棋盘共用三格板的数量为"+(result*result-1)/3+"块");
	   }
	}