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求32ms优化到16ms方法(附代码)

Posted by lyyshp at 2015-03-13 10:53:51 on Problem 1321
In Reply To:新手DFS求32ms优化到16ms方法(附代码) Posted by:bhwl14130 at 2015-02-03 16:03:04
#include <stdio.h>
int n, k, c;
char a[10][10];
bool mark[9];
void f(int x, int y, int z) 
{
	int j, i;
	if(x == k){
		for(i = y; i <= z; i++)
			for(j = 0; j < n; j++){
				if(a[i][j] == '#' && mark[j] == false) c++;
			}
	}
	else{
		for(i = y; i <= z; i++)
			for(j = 0; j < n; j++){
				if(a[i][j] == '#' && mark[j] == false){
					mark[j] = true;
					f(x+1, i+1, z+1);
					mark[j] = false;
				}
			}
	}
}
int main()
{
    int i;
	while(scanf("%d%d", &n, &k) && n+1){
		for(i = 0; i < n; i++)
			scanf("%s", a[i]);
		c = 0;
		for(i = 1; i < 9; i++)
			mark[i] = false;
		f(1, 0, n-k);
		printf("%d\n", c);
	}
	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