首页 > 搜索 > DFS搜索 > HDU 1315 Basic-DFS-[解题报告] C++
2013
12-09

HDU 1315 Basic-DFS-[解题报告] C++

Basic

问题描述 :

The programming language Ada has integer constants that look like this: 123, 8#123#, 16#abc#. These constants represent the integers 123, 83 (123 base 8) and 2739 (abc base 16). More precisely, an integer may be a decimal integer given as a sequence of one or more digits less than 10, or it may be an integer to some specific base, given as the base followed by a sequence of one or more digits less than the base enclosed by # symbols. Lower case letters from a through f are used as the digits representing 10 through 15. In Ada, the base, if specified, must be a sequence of decimal digits. For this problem, however, the base may be of any form described above so long as it represents an integer between 2 and 16 inclusive.

输入:

The first line of input contains a positive integer n. n lines follow

输出:

For each line of input, output a line "yes" if it is a valid integer constant according to the above rules; otherwise output a line containing "no". Input lines contain no spaces and are between 1 and 80 characters in length.

样例输入:

5
2#101#
2#101##123#
17#abc#
16#123456789abcdef#
16#123456789abcdef#123456789abcdef#

样例输出:

yes
yes
no
yes
no

/*
	本题用深搜,尽可能多的安排rook
*/
#include<stdio.h>
char map[4][4];
int x[20],y[20],c[20],num,n,no;
int xing(int i,int j)
{
	if(c[j]==0)
		return 0;
	if(x[i]!=x[j]&&y[i]!=y[j])
		return 0;
	if(x[i]==x[j])
	{
		int k=y[i],l=y[j],t;
		if(k>l)
		{
			t=k;
			k=l;
			l=t;
		}
		for(;k<=l;k++)
			if(map[x[i]][k]=='X')
				return 0;
		return 1;
	}
	else
	{
		int k=x[i],l=x[j],t;
		if(k>l)
		{
			t=k;
			k=l;
			l=t;
		}
		for(;k<=l;k++)
			if(map[k][y[i]]=='X')
				return 0;
		return 1;
	}
}
int he(int i)
{
	int j;
	for(j=0;j<i;j++)
		if(xing(i,j))
			return 0;
	return 1;
}
void dfs(int ii,int o)
{
	int i;
	if(ii==num)
		return;
	for(i=ii;i<num;i++)//一次试,o可否安排在i
	{
		if(he(i))//判断i处能否安排rook
		{
			c[i]=1;
			if(o>no)//o代表当前rook的数量,若大与no,就更新no
				no=o;
			dfs(i+1,o+1);//o安排在i,接着在从i+1开始往后安排第o+1个rook
			c[i]=0;
		}
	}
}
int main()
{
	int i,j;
	while(scanf("%d",&n),n)
	{
		getchar();
		num=0;
		no=0;
		for(i=0;i<n;i++)
		{
			for(j=0;j<n;j++)
			{
				map[i][j]=getchar();
				if(map[i][j]=='.')//搜集可安排棋子的位置
				{
					x[num]=i;
					y[num]=j;
					c[num]=0;
					num++;
				}
			}
			getchar();
		}
		dfs(0,1);//在从开始往后的地方,安排第1个rook
		printf("%d\n",no);
	}
	return 0;
}

解题报告转自:http://blog.csdn.net/qq172108805/article/details/6657530


,
  1. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的