che.cpp

问题描述：按照国际象棋的规则

#include<iostream>

using namespace std;

//全局变量
int p; //存放剩余的格子数
int n1, m1, final_num;//final_num用来存放不受攻击的格子总数
int m, n, r, c;//m,n分别为方格的行和列，r,c分别表示指南车数x和y
int x[100], y[100], state[100];//数组x,y用来存放指南车x的位置


void compute(int wx, int wy)//区域wx*wy空出时
{
	int rest,row_num, row_num_left, left, r0,col_num,col_num_left,i=1;
	rest = n * m - wx * wy - c;//被覆盖但未填的格数
	r0 = r - rest;//添满已覆盖的格子后剩下r0辆车
	if(r0 <= 0)//覆盖的格子尚未填满
	{
		left = wx * wy;
		if(left > final_num)
		{
			final_num = left;
		}
		return;
	}
	row_num=r0/wx;col_num=r0/wy;
	row_num_left=r0%wx;col_num_left=r0%wy;
	//r0>0,指南车x已覆盖的格子不够指南车y填充时
    
		if(row_num_left==0&&col_num_left==0) left=col_num*wy;//或者left=row_num*wx;效果等同
		else
		{
			if(row_num_left==0) //row_num_left=0,col_num_left!=0
			{
				left=row_num*wx;
			}
			else //row_num_left!=0
				if(col_num_left==0)
				{
					left=col_num*wy;
				}
				else //col_num_left!=0
				{
				
					if(wx<=wy) left=(row_num+1)*wx;
					else left=(col_num+1)*wy;
				}
		}
		
		left=wx*wy-left;

		if(left>final_num) final_num=left;
}

void Max_num(int i, int wx, int wy) 
{   
	//确定第i辆车时,有wx * wy的区域空出
	int j;
	if(i > r)//确定指南车y的位置和方向
	{

		compute(wx,wy);
		return;
	}
	for(j=1; j<=i-1; j++)
	{
		if(x[j]==x[i] && state[j]==0)//指南车位置在同一行且攻击方向为列攻击，将指南车i的方向置为列攻击
		{
			
			state[i] = 0;
			Max_num(i+1,wx,wy);
			return; 
		}
		if(y[j]==y[i] && state[j]==1)//指南车位置在同一列且攻击方向为行攻击，将指南车i的方向置为行攻击
		{
			state[i] = 1;
			Max_num(i+1,wx,wy);
			return; 
		}
	}
	
	state[i] = 1;//指南车x中第i个指南车的方向为行攻击
	if(wx*(wy-1) > final_num)
		Max_num(i+1, wx, wy-1);
	state[i] = 0;//指南车x中第i个指南车的方向为列攻击
	if((wx-1)*wy > final_num)
		Max_num(i+1, wx-1, wy);
	state[i] = 1;
}

int main()
{

	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	cin>>m>>n>>r>>c;
	p = m * n - r - c;//p为总格子数减去所占用的格子数
	final_num = -1;
	for(int i=1; i<=r; i++)
		cin>>x[i]>>y[i];
	if(p == 0 || p ==1) final_num = p;
	else
	{
		Max_num(1,m,n);
	}
	cout<<final_num<<endl;
	
	return 0;
}