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大学生程序设计竞赛训练》暑期课面向全球招生!

我的超时,有没有大神看看为什么

Posted by 18802235956 at 2017-01-16 19:11:38 on Problem 1321
#include<stdio.h>
#include<stdlib.h>
int n,k;
int data[9][9] = {0};
int num = 0;
int op[65][9][2] = {0};
int cun[9][2] = {0};
bool issafe(int x,int y);
void DFS(int step);
int main()
{
	char w;
	freopen("1321.txt","r",stdin);
	while(1)
	{
		scanf("%d",&n);
		scanf("%d\n",&k);
		if(n == -1 && k == -1){
			break;
		}
		for(int i = 0;i < n;i++)
		{
			for(int j = 0;j < n;j++)
			{
				scanf("%c",&w);
				if(w == '.'){
					data[i][j] = 0;
				}
				else{
					data[i][j] = 1;
				}
			}
			scanf("%c",&w);
		}
		DFS(0);
		printf("%d\n",num);
		for(int e = 0;e <= num;e++)
		{
			for(int m = 0;m < n;m++)
			{
				for(int l = 0;l < n;l++)
				{
					data[m][l] = 0;
				}
				cun[m][0] = 0;
				cun[m][1] = 0;
				op[e][m][0] = 0;
				op[e][m][1] = 0;
			}
		}
		
		num = 0;
	}
	return 0;
}
void DFS(int step)
{
	if(step == k){
		int q = 0;
		bool ret = true;
		for(int t = 0;t < num;t++)
		{
			q = 0;
			for(int k = 0;k < step;k++)
			{
				for(int f = 0;f < step;f++)
				{
					if(cun[k][0] == op[t][f][0] && cun[k][1] == op[t][f][1]){
						q++;
						break;
					}
				}
			}
			if(q == step){
				ret = false;
				break;
			}
		}
		if(ret){
			for(int k = 0;k < step;k++)
			{
				op[num][k][0] = cun[k][0];
				op[num][k][1] = cun[k][1];
			}
			num++;
		}
		return;
	}
	for(int i = 0;i < n;i++)
	{
		for(int j = 0;j < n;j++)
		{
			if(data[i][j] == 1 && issafe(i,j)){
				data[i][j] = 2;
				cun[step][0] = i;
				cun[step][1] = j;
				DFS(step + 1);
				data[i][j] = 1;
				cun[step][0] = 0;
				cun[step][1] = 0;
			}
		}
	}
}
bool issafe(int x,int y)
{
	bool ret = true;
	for(int i = 0;i < n;i++)
	{
		if(data[x][i] == 2 || data[i][y] == 2){
			ret = false;
			return ret;
		}
	}
	return ret;
}

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