首页 > 代码库 > HDU 1045 - Fire Net （最大独立集）

HDU 1045 - Fire Net （最大独立集）

2024-07-02 10:11:07   230人阅读

题意：给你一个正方形棋盘。每个棋子可以直线攻击，除非隔着石头。现在要求所有棋子都不互相攻击，问最多可以放多少个棋子。

 

这个题可以用搜索来做。每个棋子考虑放与不放两种情况，然后再判断是否能互相攻击来剪枝。最后取可以放置的最大值。

这里我转化成求最大独立集来做。

首先将每个空地编号，对于每个空地，与该位置可以攻击到的空地连边。找最多的空地使得不互相攻击，即求该图的最大独立集。与搜索做法基本一致，但是说法略有不同。

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<algorithm>
 5 #include<cstdlib>
 6 #include<cstdio>
 7 #include<vector>
 8 using namespace std;
 9 char grid[5][5];
10 bool gl[30][30];
11 int g[5][5];
12 int n,cn,ans;
13 bool col[30];
14 void init()
15 {
16     memset(gl,0,sizeof(gl));
17     cn=0;
18     for(int i=0; i<n; ++i)
19         for(int j=0; j<n; ++j)
20             if(grid[i][j]==‘.‘)
21                 g[i][j]=++cn;
22             else g[i][j]=0;
23     for(int i=0; i<n; ++i)
24         for(int j=0; j<n; ++j)
25             if(grid[i][j]==‘.‘)
26             {
27                 int &now=g[i][j];
28                 for(int k=j+1; k<n&&g[i][k]; ++k)
29                     gl[now][g[i][k]]=true;
30                 for(int k=j-1; k>=0&&g[i][k]; --k)
31                     gl[now][g[i][k]]=true;
32                 for(int k=i+1; k<n&&g[k][j]; ++k)
33                     gl[now][g[k][j]]=true;
34                 for(int k=i-1; k>=0&&g[k][j]; --k)
35                     gl[now][g[k][j]]=true;
36             }
37     ans=0;
38     memset(col,0,sizeof(col));
39 
40 }
41 void dfs(int d,int res)
42 {
43     if(d>cn) ans=max(ans,res);
44     else
45     {
46         bool ok=true;
47         for(int i=1; i<=cn; ++i)
48             if(gl[d][i]&&col[i]) ok=false;
49         if(ok)
50         {
51             col[d]=true;
52             dfs(d+1,res+1);
53             col[d]=false;
54         }
55         dfs(d+1,res);
56     }
57 }
58 int main()
59 {
60     while(scanf("%d",&n)!=EOF&&n)
61     {
62         for(int i=0; i<n; ++i)
63             scanf("%s",grid[i]);
64         init();
65         dfs(1,0);
66         printf("%d\n",ans);
67     }
68     return 0;
69 }
View Code

 

 


联系
我们