[dfs][模拟]hdoj 5031

大致题意：

 右侧每个格子内的数字代表的是左边对应点上经过的直线数，给出右侧的格子，求最少有多少条直线，每条直线最少经过三个点，最多有14条直线。

 

大致思路：

    正确的做法应该是先枚举出所有的直线，再dfs，参考：http://blog.csdn.net/u013491262/article/details/39522799

    我这里在dfs的过程中枚举每条直线的起点和斜率，导致编码的复杂性太高，卡了好久题 23333

/***********************************************************
    > File Name: main.cpp
    > Author: bbezxcy
    > Mail:[e-mail]
    > Created Time: Wed 24 Sep 2014 06:47:06 PM CST
 **********************************************************/
//只枚举起点和斜率
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <cmath>
using namespace std;
map<double,bool>db;
int mapp[60][60],res;
int n,m;
bool check(int x,int y,int xpp,int ypp){
    int xx=x-xpp,yy=y-ypp,tim=0;
    while(x>=0&&y>=0&&x<=n&&y<=m){
        tim++;
        if(!mapp[x][y]){
            return 0;
        }
        x+=xpp;
        y+=ypp;
    }
    if(xx>=0&&yy>=0&&xx<=n&&yy<=m)return 0;
    if(tim<3){
        return 0;
    }
    return 1;
}
int del(int x,int y,int xpp,int ypp){
    //int xx=x-xpp,yy=y-ypp;
    int sss=0;
    while(x>=0&&y>=0&&x<=n&&y<=m){
        mapp[x][y]--;
        x+=xpp;
        y+=ypp;
        sss++;
    }
    return sss;
}
void add(int x,int y,int xpp,int ypp){
    while(x>=0&&y>=0&&x<=n&&y<=m){
        mapp[x][y]++;
        x+=xpp;
        y+=ypp;
    }
}
void dfs(int dep,int last){
    if(dep>=res){
        return;
    }
    if(last==0){
        res=min(dep,res);
        return;
    }
    int i,j,ss;
    bool flag=0;
    for(i=0;i<=n&&!flag;i++){
        for(j=0;j<=m&&!flag;j++){
            if(mapp[i][j]){   //枚举起点
                flag=1;
                if(i==0){
                    if(check(i,j,1,0)){
                        ss=del(i,j,1,0);
                        dfs(dep+1,last-ss);
                        add(i,j,1,0);
                    }
                }
                if(j==0){
                    if(check(i,j,0,1)){
                        ss=del(i,j,0,1);
                        dfs(dep+1,last-ss);
                        add(i,j,0,1);
                    }
                }
                db.clear();
                for(int p=i+1;p<=n;p++){
                    for(int q=0;q<=m;q++){
                        if(mapp[p][q]&&q!=j&&p!=i){
                            int a=p-i,b=q-j;
                            if(db[(b*1.0)/(a*1.0)]!=0)continue;
                            db[(b*1.0)/(a*1.0)]=1;
                            if(check(i,j,a,b)){
                                ss=del(i,j,a,b);
                                dfs(dep+1,last-ss);
                                add(i,j,a,b);
                            }
                        }
                    }
                }
            }
        }
    }
}
int main(){
    int i,j,k,cas,sum;
    scanf("%d",&cas);
    while(cas--){
        scanf("%d%d",&n,&m);
        sum=0;
        res=14;
        for(i=0;i<=n;i++){
            for(j=0;j<=m;j++){
                scanf("%d",&mapp[i][j]);
                sum+=mapp[i][j];
            }
        }
        res=min(14,sum/3);
        dfs(0,sum);
        printf("%d\n",res);
    }
    return 0;
}