当前位置:首页 > 资讯 > info6 > 正文

zju 1002

发表于: 2014-04-05   作者:chen_xinjia   来源:转载   浏览:
摘要: //zju1002 // #include"stdafx.h" #include #include usingnamespacestd; intN=4; intMax=0; chara[5][5]; intjudge(introw,intcol)//测试该坐标是否可以放置返回0可放置,返回1不可放置 { for(inti=row-1;i>=0;i--)//测试该行之前的位置 { if(a[i]
// 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>

zju 1002

版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号