Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

Re:DFS一次AC,附代码

Posted by heyukai at 2018-03-10 15:50:00 on Problem 1321
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 10
using namespace std;
int n,k,ans;bool a[maxn][maxn],b[maxn];
inline int read()
{
	bool f=0;char ch=getchar();
	while (ch<'0'||ch>'8') f^=!(ch^45),ch=getchar();
	return f? (~(ch^48))+1:ch^48;
}
inline bool fchar()
{
	char ch=getchar();
	while (ch^'#'&&ch^'.') ch=getchar();
	return ch^'.';
}
void DFS(int l,int stp)
{
	if (stp==k){ans++;return;}
	for (int i=l+1;i<=n;i++)
	  for (int j=1;j<=n;j++) if (a[i][j]&&!b[j])
		b[j]=1,DFS(i,stp+1),b[j]=0;
}
int main()
{
	while ((n=read())!=-1&&(k=read())!=-1)
	{
		memset(a,0,sizeof(a));memset(b,0,sizeof(b));ans=0;
		for (int i=1;i<=n;i++)
		  for (int j=1;j<=n;j++) a[i][j]=fchar();
		DFS(0,0);
		printf("%d\n",ans);
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator