pku1315.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
char map[6][6];
int N;
int Max;

void DFS(int p, int n)
{
	int x, y, i, OK;
	x = p / N;
	y = p % N;
	if (n > Max)
	{
		Max = n;
	}

	if (p > N * N - 1)
	{
		return;
	}

	DFS(p + 1, n);

	if (map[x][y] != '.')
	{
		return;
	}

	for (i = y - 1; i >= 0; i--)
	{
		if (map[x][i] == 'c')
		{
			return;
		}
		if (map[x][i] == 'X')
		{
			break;
		}
	}

	for (i = x - 1; i >= 0; i--)
	{
		if (map[i][y] == 'c')
		{
			return;
		}
		if (map[i][y] == 'X')
		{
			break;
		}
	}
	
	map[x][y] = 'c';
	DFS(p + 1, n + 1);
	map[x][y] = '.';
}

int main()
{
	int i;
	while (scanf("%d", &N), N)
	{
		Max = 0;
		for (i = 0; i < N; i++)
		{
			scanf("%s", map[i]);
		}
		DFS(0, 0);
		printf("%d\n", Max);
	}
	return 0;
}