碉堡放置-图的搜索

// Fire.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include "iostream"
#define NUM 100
using namespace std;

char cMap[NUM][NUM];
int iBest;
int n;

bool CanPut(int x,int y)
{
	int i;
	for(i=x-1;i>=0;i--)
	{
		if(cMap[i][y]=='o')
			return false;
		if(cMap[i][y]=='x')
			break;
	}
	for(i=y-1;i>=0;i--)
	{
		if(cMap[x][i]=='o')
			return false;
		if(cMap[x][i]=='x')
			break;
	}
	return true;
}

void Solve(int k,int current)
{
	int x,y;
	if(k==n*n)
	{
		if(current>iBest)
		{
		iBest=current;
		return;
		}
	}
	else
	{
		x=k/n;
		y=k%n;
		if(cMap[x][y]=='.'&&CanPut(x,y))
		{
			cMap[x][y]='o';
			Solve(k+1,current+1);
			cMap[x][y]='.';
		}
		Solve(k+1,current);
	}

}



int _tmain(int argc, _TCHAR* argv[])
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
			cin>>cMap[i][j];
	}
	Solve(0,0);
	
	cout<<iBest<<endl;
	system("pause");
	return 0;
}