main.cpp

一个acm算法题目 问题描述： 有一个黑盒子

#include <iostream.h>
#include <memory.h>
#include <fstream.h>

#define MAXX 15
#define MAXY 10
#define MAXXY 24

class Sys
{
private:
	int* x;
	int* y;
	int* xy;//逆时针x->y
	int* yx;
	int tx[MAXX];
	int ty[MAXY];
	int txy[MAXXY];//逆时针x->y 左上角为0,0
	int tyx[MAXXY];//左下角为0,0
	int IsPlaced[MAXX][MAXY];
	bool ok;
public:
	int Result[MAXX][MAXY];
	Sys(int* input_x,int* input_y,int* input_xy,int* input_yx);
	void backtrack(int CurrentX,int CurrentY);
};

Sys::Sys(int* input_x,int* input_y,int* input_xy,int* input_yx)
{
	ok = false;
	memset(tx,0,MAXX*sizeof(int));
	memset(ty,0,MAXY*sizeof(int));
	memset(txy,0,MAXXY*sizeof(int));
	memset(tyx,0,MAXXY*sizeof(int));

	x = input_x;
	y = input_y;
	xy = input_xy;
	yx = input_yx;

	for(int i=0;i<MAXX;i++)
		for(int j=0;j<MAXY;j++)
			IsPlaced[i][j]=-1;//-1代表没有用,0代表没有放,1放了
}

void Sys::backtrack(int CurrentX,int CurrentY)
{
	CurrentX++;
	if(CurrentX==MAXX)
	{
		CurrentX=0;
		CurrentY++;
	}
	//到达底部处理
	if(CurrentY==MAXY)
	{
		for(int i=0;i<MAXX;i++)
			if(tx[i]!=x[i])
				return;
		for(int i=0;i<MAXY;i++)
			if(ty[i]!=y[i])
				return;
		for(int i=0;i<MAXXY;i++)
		{
			if(txy[i]!=xy[i])
				return;
			if(tyx[i]!=yx[i])
				return;
		}
		for(int i=0;i<MAXX;i++)
			for(int j=0;j<MAXY;j++)
				Result[i][j] = IsPlaced[i][j];
		ok = true;
		return;
	}

	/////////////////////////////////////////////////////
	//不够的情况
	//x
	if(tx[CurrentX]+MAXY-CurrentY<x[CurrentX])
		return;

	//y
	if(ty[CurrentY]+MAXX-CurrentX<y[CurrentY])
		return;

	//xy
	int counts = 1;
	int m=CurrentX;
	int n=CurrentY;
	while(m>=0&&n<MAXY)
	{
		m--;
		n++;
		counts++;
	}
	if(txy[CurrentX+CurrentY]+counts<xy[CurrentX+CurrentY])
		return;

	//yx
	counts = 1;
	m=CurrentX;
	n=CurrentY;
	while(m<MAXX&&n<MAXY)
	{
		m++;
		n++;
		counts++;
	}
	if(tyx[CurrentX-CurrentY+MAXY-1]+counts<yx[CurrentX-CurrentY+MAXY-1])
		return;
	/////////////////////////////////////////////////////
	//必须放情况
	if(tx[CurrentX]+MAXY-CurrentY==x[CurrentX])
		IsPlaced[CurrentX][CurrentY]=1;

	//y
	if(ty[CurrentY]+MAXX-CurrentX==y[CurrentY])
		IsPlaced[CurrentX][CurrentY]=1;

	//xy
	counts = 1;
	m=CurrentX;
	n=CurrentY;
	while(m>=0&&n<MAXY)
	{
		m--;
		n++;
		counts++;
	}
	if(txy[CurrentX+CurrentY]+counts==xy[CurrentX+CurrentY])
		IsPlaced[CurrentX][CurrentY]=1;

	//yx
	counts = 1;
	m=CurrentX;
	n=CurrentY;
	while(m<MAXX&&n<MAXY)
	{
		m++;
		n++;
		counts++;
	}
	if(tyx[CurrentX-CurrentY+MAXY-1]+counts==yx[CurrentX-CurrentY+MAXY-1])
		IsPlaced[CurrentX][CurrentY]=1;
	/////////////////////////////////////////////////////

	//放满情况
	if(tx[CurrentX]==x[CurrentX])
	{
		IsPlaced[CurrentX][CurrentY]=0;
	}
	if(ty[CurrentY]==y[CurrentY])
	{
		IsPlaced[CurrentX][CurrentY]=0;
	}
	//xy
	if(txy[CurrentX+CurrentY]==xy[CurrentX+CurrentY])
	{
		IsPlaced[CurrentX][CurrentY]=0;
	}
	//yx
	if(tyx[CurrentX-CurrentY+MAXY-1]==yx[CurrentX-CurrentY+MAXY-1])
	{
		IsPlaced[CurrentX][CurrentY]=0;
	}

	//一定放的情况
	if(IsPlaced[CurrentX][CurrentY]==1)
	{
		tx[CurrentX]++;
		ty[CurrentY]++;
		txy[CurrentX+CurrentY]++;
		tyx[CurrentX-CurrentY+MAXY-1]++;

		backtrack(CurrentX,CurrentY);

		IsPlaced[CurrentX][CurrentY]=-1;
		tx[CurrentX]--;
		ty[CurrentY]--;
		txy[CurrentX+CurrentY]--;
		tyx[CurrentX-CurrentY+MAXY-1]--;
		return;
	}
	//一定不放的情况
	if(IsPlaced[CurrentX][CurrentY]==0)
	{
		backtrack(CurrentX,CurrentY);
		IsPlaced[CurrentX][CurrentY]=-1;
	}
	else
	{
		//回溯有先后,先放,后不放,用一个方法剪枝
		//此点是所要节点
		IsPlaced[CurrentX][CurrentY]=1;
		tx[CurrentX]++;
		ty[CurrentY]++;
		txy[CurrentX+CurrentY]++;
		tyx[CurrentX-CurrentY+MAXY-1]++;

		backtrack(CurrentX,CurrentY);

		IsPlaced[CurrentX][CurrentY]=0;
		tx[CurrentX]--;
		ty[CurrentY]--;
		txy[CurrentX+CurrentY]--;
		tyx[CurrentX-CurrentY+MAXY-1]--;
		if(ok==true)
			return;

		//不放,进入下一层
		IsPlaced[CurrentX][CurrentY]=0;
		backtrack(CurrentX,CurrentY);
		IsPlaced[CurrentX][CurrentY]=-1;
		if(ok==true)
			return;
	}
}

main()
{
	ifstream f("input.txt",ios::in);
	ofstream of("output.txt",ios::out);
	int num[4][30];
	int totalx=0;
	int total;
	while(!f.eof())
	{
		total=0;
		char c=0;
		for(int i=0;(int)c!=10&&!f.eof();i++)
		{
			f>>num[totalx][total];
			f.read(&c,1);
			total++;
		}
		totalx++;
	}

	Sys s(num[0],num[1],num[2],num[3]);
	s.backtrack(-1,0);
	for(int i=0;i<MAXY;i++)
	{
		for(int j=0;j<MAXX;j++)
		{
			if(s.Result[j][i]==1)
				of<<"*";
			else
				of<<' ';
		}
		of<<endl;
	}
}