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

最后加一条 = 260ms -> 250ms 收工

Posted by wcfairytale at 2011-10-10 01:36:45 on Problem 3740
In Reply To:加一条 = 500ms -> 260ms Posted by:wcfairytale at 2011-10-10 01:24:09
#include<stdio.h>
#include<string.h>

int map[17][301];
int rn[17];
int cn[301];
bool is_useful[17];
bool flag;
int M,N;
int i,j;
int tn[301];
int rest[17];

int is_rest_has[17][301];

void dfs(int depth, int total)
{
	if(flag)return;//has found

	if(total == N) //found!!
	{
		flag = true;
		return;
	}

	if(depth == M)return;
	
	if(total + rest[depth] < N)return;//not enough 1

	for(i=0;i<N;i++)
	{
		if(tn[i] == 0 && is_rest_has[depth][i] == 0)return; //rest rows, no 1 on coli

		if(tn[i] !=0 && map[depth][i] !=0)//more than one 1
		{
			dfs(depth+1,total);
			return;
		}
	}

	if(!is_useful[depth]) //rn[depth] = 0
	{
		dfs(depth+1,total);
		return;
	}
	
	if(total + rn[depth] > N)//not ok
	{
		dfs(depth+1,total);
		return;
	}
	//dont use the row
	dfs(depth+1,total);

	if(flag)return;//has found

	//use the row
	for(i=0;i<N;i++)
		tn[i] += map[depth][i];

	dfs(depth+1,total+rn[depth]);

	for(i=0;i<N;i++)
		tn[i] -= map[depth][i];
}
int main()
{
	int i,j;
	
	while(scanf("%d%d",&M,&N) != EOF)
	{
		for(i=0;i<M;i++)
		{
			rn[i]=0;
			is_useful[i]=true;
		}
		for(i=0;i<N;i++)
		{
			cn[i]=0;
			tn[i]=0;
		}
		
		flag = false;
	
		for(i=0;i<M;i++)
			for(j=0;j<N;j++)
			{
				scanf("%d",&map[i][j]);
			
				is_rest_has[i][j]=0;

				if(map[i][j]!=0)
				{
					rn[i]++; 
					cn[j]++;
				}
			}
		for(i=0;i<N;i++)is_rest_has[M-1][i]=map[M-1][i];
		for(i=M-2;i>=0;i--)
		{
			for(j=0;j<N;j++)
			{
				if(is_rest_has[i+1][j] || map[i][j])
					is_rest_has[i][j] = 1;
			}
		}

		rest[M-1] = rn[M-1];
		for(i=M-2;i>=0;i--)
			rest[i] = rest[i+1]+rn[i];

		//if a rown == 0 then the row is useless
		for(i=0;i<M;i++)
			if(rn[i]==0)is_useful[i]=false;

		//if a coln == 0 then impossible
		for(i=0;i<N;i++)if(cn[i]==0)break;
		if(i!=N)
		{
			printf("It is impossible\n");
			continue;
		}
		
		dfs(0,0);

		if(flag)
			printf("Yes, I found it\n");
		else 
			printf("It is impossible\n");
	}

	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