首页 > 代码库 > HDU_1045 Fire Net
HDU_1045 Fire Net
传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1045
题意:
4 .X.. .... XX.. ....
给你n*n的图,‘X‘表示墙,在图中填黑点,一行(或一列)中不能有两可以直达的点(即:一行(列)中任意两点有墙相隔。
思路:由于n<=4,所以直接二进制枚举了。然后用check(int cur)函数判断是否可行。
//据说这题是贪心。。。。
代码:
/************************************************ * Author: Ac_sorry * File: * Create Date: * Motto: One heart One life * CSDN: http://blog.csdn.net/code_or_code *************************************************/ #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<cstdlib> #include<vector> #include<string> #include<utility> #include<map> #include<set> #include<queue> #include<stack> #define INF 0x3f3f3f3f #define MOD 1000000007 #define seed_ 131 #define eps 1e-8 #define mem(a,b) memset(a,b,sizeof a) #define w(i) tree[i].w #define ls(i) tree[i].ls #define rs(i) tree[i].rs using namespace std; typedef long long LL; const int N=100010; char gra[10][10]; int vis[10][10]; int n; int check(int cur) { int cnt=0; mem(vis,0); for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(gra[i][j]=='X') vis[i][j]=2; } } for(int i=0;i<n*n;i++) { if(cur&(1<<i)) { if(vis[i/n][i%n]) return -1; //cout<<i<<"-"<<endl; vis[i/n][i%n]=1; cnt++; } } int flag; for(int i=0;i<n;i++) { flag=0; for(int j=0;j<n;j++) { if(vis[i][j]==1) { if(flag) return -1; flag=1; } else if(vis[i][j]==2) flag=0; } } for(int j=0;j<n;j++) { flag=0; for(int i=0;i<n;i++) { if(vis[i][j]==1) { if(flag) return -1; flag=1; } else if(vis[i][j]==2) flag=0; } } return cnt; } int main() { while(scanf("%d",&n)==1) { if(n==0) break; for(int i=0;i<n;i++) scanf("%s",gra[i]); int ans=0; for(int i=0;i<(1<<(n*n));i++) { ans=max(ans,check(i)); //cout<<i<<"--\n"; } printf("%d\n",ans); } return 0; }
HDU_1045 Fire Net
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。