大致题意:
右侧每个格子内的数字代表的是左边对应点上经过的直线数,给出右侧的格子,求最少有多少条直线,每条直线最少经过三个点,最多有14条直线。
大致思路:
正确的做法应该是先枚举出所有的直线,再dfs,参考:http://blog.csdn.net/u013491262/article/details/39522799
我这里在dfs的过程中枚举每条直线的起点和斜率,导致编码的复杂性太高,卡了好久题 23333
/*********************************************************** > File Name: main.cpp > Author: bbezxcy > Mail:522736096@qq.com > 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; }
相关推荐
HDOJ题目分类HDOJ题目分类HDOJ题目分类
ACM ICPC HDOJ1002
ACM ICPC HDOJ1001
hdoj1001标程
hdoj上的资源,代码有注释,很不错的哦
hdoj1004,解题代码,答案代码,欢迎下载
ACM ICPC HDOJ1003
ACM ICPC HDOJ1008
杭州电子科技大学hdoj1002,大整数相加问题
杭州电子科大HDOJ
c语言 最短路 是hdoj上的一个最短路问题,写的很牛
ACM ICPC HDOJ1000
hdoj解题代码,题目为1000-1050
一些HDOJ上的DP题目的小总结,但愿能帮到那些想专攻DP的人吧
codj,hdoj的源码(50-60题)
hdoj 2013 多校训练3标程+解题报告
HDOJ 源代码 包含几百道HDOJ题目源码
hdoj1005 Number Sequence, 杭州电子科技大学oj题目代码
杭电OJ(1000-1099) AC 代码
HDOJ使用指南——公开版.docHDOJ使用指南——公开版.docHDOJ使用指南——公开版.doc