chessboard.cpp

关于棋盘覆盖问题的算法设计与分析

#include<iostream>
#include<iomanip>
using namespace std;

int Board[16][16];
int tile=1;

void ChessBoard(int tr,int tc,int dr,int dc,int size)
{
	if (size==1) return;
		int t=tile++,s=size/2;

	if (dr<tr+s && dc<tc+s)
		ChessBoard(tr,tc,dr,dc,s);
	else {Board[tr+s-1][tc+s-1]=t;
	ChessBoard(tr,tc,tr+s-1,tc+s-1,s);}

	if(dr<tr+s && dc>=tc+s)
		ChessBoard(tr,tc+s,dr,dc,s);
	else{Board[tr+s-1][tc+s]=t;
	ChessBoard(tr,tc+s,tr+s-1,tc+s,s);}

	if(dr>=tr+s && dc<tc+s)
		ChessBoard(tr+s,tc,dr,dc,s);
	else{Board[tr+s][tc+s-1]=t;
	ChessBoard(tr+s,tc,tr+s,tc+s-1,s);}

	if(dr>=tr+s && dc>=tc+s)
		ChessBoard(tr+s,tc+s,dr,dc,s);
	else{Board[tr+s][tc+s]=t;
	ChessBoard(tr+s,tc+s,tr+s,tc+s,s);}
}

void print(int n)
{
	int i,j;
	for (i=0;i<n;i++)
	{
		for (j=0;j<n;j++)
		
		cout<<setw(2)<<Board[i][j]<<"     ";
		cout<<endl;
	}
}

void main()
{
	int tr=0,tc=0,dr,dc,size;
	cout<<"请输入棋盘的大小：";
	cin>>size;
	cout<<"请输入特殊方块的行号：";
	cin>>dr;
	cout<<"请输入特殊方块的列号：";
	cin>>dc;
	Board[dr-1][dc-1]=0;
	ChessBoard(tr,tc,dr-1,dc-1,size);
	print(size);
}