枚举角度DFS。。。。

Lines

You play a game with your friend. He draws several lines on the paper with n×m square grids (see the left figure). After that, he writes down the number of lines passing through every integer coordinate in a matrix (see the right figure).


The number of lines passing though coordinate (i,j) is written in cell (i,j) in the right figure.(i,j both start from 0).

You are given the matrix written by your friend. You need to figure out the possible minimal number of lines your friend drew on the paper.

1
5 4
0 1 0 0 1
0 1 0 1 0
2 1 1 0 0
0 3 1 0 0
1 1 1 0 1
0 1 0 1 0

4

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>

using namespace std;

map<double,bool> DB;
int n,m,ans;
int mp[60][60];

inline bool is_in(int x,int y)
{
	if(x>=0&&x<n&&y>=0&y<m) return true;
	return false;
}

void dfs(int deep,int remain)
{
	if(deep>=ans) return ;
	if(remain==0)
	{
		ans=min(ans,deep);
		return ;
	}
	bool flag=false;
	for(int i=0;i<n&&!flag;i++)
	{
		for(int j=0;j<m&&!flag;j++)
		{
			if(mp[i][j])
			{
				flag=true;
				if(i==0)
				{
					int jian=0;
					for(int p=0;p<n;p++)
					{
						if(mp[p][j]) jian++;
						else break;
					}
					if(jian==n)
					{
						for(int p=0;p<n;p++) mp[p][j]--;
						dfs(deep+1,remain-n);
						for(int p=0;p<n;p++) mp[p][j]++;
					}
				}

				if(j==0)
				{
					int jian=0;
					for(int q=0;q<m;q++)
					{
						if(mp[i][q]) jian++;
						else break;
					}
					if(jian==m)
					{
						for(int q=0;q<m;q++) mp[i][q]--;
						dfs(deep+1,remain-m);
						for(int q=0;q<m;q++) mp[i][q]++;
					}
				}

				DB.clear();

				for(int p=i+1;p<n;p++)
				{
					for(int q=0;q<m;q++)
					{
						if(mp[p][q]&&q!=j)
						{
							int x=p-i,y=q-j;
							double slope=y*1./x;
							if(DB[slope]==true) continue;
							DB[slope]=true;

							int cnt=0;
							while(is_in(i+cnt*x,j+cnt*y)&&mp[i+cnt*x][j+cnt*y]) cnt++;
							if(is_in(i-x,j-y)) continue;
							if(is_in(i+cnt*x,j+cnt*y)) continue;
							if(cnt<3) continue;

							for(int c=0;c<cnt;c++) mp[i+c*x][j+c*y]--;
							dfs(deep+1,remain-cnt);
							for(int c=0;c<cnt;c++) mp[i+c*x][j+c*y]++;
						}
					}
				}
			}
		}
	}
}

int main()
{
	int T_T;
	scanf("%d",&T_T);
	while(T_T--)
	{
		scanf("%d%d",&n,&m);
		n++; m++; int sum=0;
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<m;j++)
			{
				scanf("%d",&mp[i][j]);
				sum+=mp[i][j];
			}
		}
		ans=min(14,sum/3);
		dfs(0,sum);
        printf("%d\n",ans);
	}
	return 0;
}

HDOJ 5031 Lines

原文：http://blog.csdn.net/ck_boss/article/details/39530207