zju 1002

// zju 1002
//

#include "stdafx.h"
#include <string>
#include <iostream>

using namespace std;
int N = 4;
int Max = 0;
char a[5][5];
int judge(int row, int col)//测试该坐标是否可以放置 返回 0 可放置，返回 1 不可放置
{
	for (int i = row - 1; i >= 0; i--)//测试该行之前的位置
	{
		if (a[i][col] == '@')return 1;//不行
		if (a[i][col] == 'X')break;

	}
	for (int i = col - 1; i >= 0; i--)
	{
		if (a[row][i] == '@')return 1;
		if (a[row][i] == 'X')break;
	}
	return 0;
}
void DFS(int pos, int count)
{
	int row, col;
	if (pos == N*N)
	{
		if (Max < count)
		{
			Max = count; return;
		}
	}
	else
	{//计算出行列坐标
		row = pos / N;
		col = pos % N;
		//测试该位置是否可行
		if (!judge(row, col)&&a[row][col]=='.')
		{
			a[row][col] = '@';
			DFS(pos + 1, count+1);
			a[row][col] = '.';//恢复数据
		}
		DFS(pos + 1, count);//该位置不放置
	}
}

int main()
{
	
	while (scanf_s("%d",&N)!=EOF&&N)
	{
		memset(a, 0, sizeof(a));//快速清零
		for (int i = 0; i < N; i++)
		{

			for (int j = 0; j < N; j++)
			{
				//scanf_s("%c", a[i][j]);
				cin >> a[i][j];
			}
		}
		DFS(0, 0);
		cout << Max << endl;
		Max = 0;
	}
	return 0;
}

老师还说了一种改良算法，以后有空再写。。。又是只加了几句而已。。。

AC 记得#include <stdio.h>