首页 > 代码库 > HDU-5031-Lines(DFS)

HDU-5031-Lines(DFS)

2024-07-23 14:33:25   213人阅读

Problem Description
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.
 

Input
The first line of the input contains an integer T indicating the number of test cases( 0 < T <= 10).

For each test case, the first line contains two integers n, m (1 ≤ n, m ≤ 50) representing the size of the grids on the paper. The following (n+1) × (m+1) numbers is what your friend writes. It is guaranteed that the number of lines your friend draws does not exceed 14. Each line passes through integer coordinates at least three times.
 

Output
For each test case, you need to output the minimal number of lines your friend drew on the paper in a single line.
 

Sample Input
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
 

Sample Output
4
 

Source
2014 ACM/ICPC Asia Regional Guangzhou Online
 

思路：枚举经过当前点的所有可能直线即可。详见代码。

#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;

int mp[55][55],ans,n,m,sum;

map<double,bool>db;//用来根据斜率判重

void dfs(int dep,int remain)
{
    if(dep>=ans) return;

    if(!remain)
    {
        ans=min(ans,dep);

        return;
    }

    int i,j,p,q,cnt;
    bool flag=0;

    for(i=0;i<n && !flag;i++)
    {
        for(j=0;j<m && !flag;j++)
        {
            if(mp[i][j])
            {
                flag=1;//找到一个点即可，我们要枚举的是经过它的可行直线

                if(i==0)//经过改点的竖直直线
                {
                    for(p=i;p<n;p++) if(!mp[p][j]) break;

                    if(p==n)
                    {
                        for(p=i;p<n;p++) mp[p][j]--;

                        dfs(dep+1,remain-n);

                        for(p=i;p<n;p++) mp[p][j]++;
                    }
                }

                if(j==0)//经过改点的水平直线
                {
                    for(p=j;p<m;p++) if(!mp[i][p]) break;

                    if(p==m)
                    {
                        for(p=j;p<m;p++) mp[i][p]--;

                        dfs(dep+1,remain-m);

                        for(p=j;p<m;p++) mp[i][p]++;
                    }

                }

                db.clear();//清空状态

                for(p=i+1;p<n;p++)
                {
                    for(q=0;q<m;q++)
                    {
                        if(mp[p][q] && p!=i && q!=j)
                        {
                            int x=p-i,y=q-j;

                            if(!db[double(y)/x]) db[double(y)/x]=1;//该斜率直线是否已经找过
                            else continue;

                            cnt=1;

                            while(i+cnt*x>=0 && i+cnt*x<n && j+cnt*y>=0 && j+cnt*y<m && mp[i+cnt*x][j+cnt*y]) cnt++;

                            if(i+cnt*x>=0 && i+cnt*x<n && j+cnt*y>=0 && j+cnt*y<m) continue;//如果后面的不能连续
                            if(i-x>=0 && i-x<n && j-y>=0 && j-y<m) continue;//如果前面的不能连续
                            if(cnt<3) continue;//经过的点少于3个


                            cnt=1;

                            while(i+cnt*x>=0 && i+cnt*x<n && j+cnt*y>=0 && j+cnt*y<m)
                            {
                                mp[i+cnt*x][j+cnt*y]--;

                                cnt++;
                            }

                            mp[i][j]--;

                            dfs(dep+1,remain-cnt);

                            mp[i][j]++;

                            cnt=1;

                            while(i+cnt*x>=0 && i+cnt*x<n && j+cnt*y>=0 && j+cnt*y<m)
                            {
                                mp[i+cnt*x][j+cnt*y]++;

                                cnt++;
                            }
                        }
                    }
                }
            }
        }
    }
}

int main()
{
    int T,i,j;

    scanf("%d",&T);

    while(T--)
    {
        scanf("%d%d",&n,&m);

        n++;
        m++;

        sum=0;

        for(i=0;i<n;i++)
        {
            for(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);
    }
}


HDU-5031-Lines(DFS)


联系
我们