HDU 5556 最大独立集

  1 #include <iostream>
  2 #include <vector>
  3 #include <algorithm>
  4 #include <string>
  5 #include <string.h>
  6 #include <stdio.h>
  7 #include <queue>
  8 #include <stack>
  9 #include <map>
 10 #include <set>
 11 #include <cmath>
 12 #include <ctime>
 13 #include <cassert>
 14 #include <sstream>
 15 using namespace std;
 16 
 17 const int N=110;
 18 
 19 char s[N][N];
 20 int id[N][N];
 21 int dx[]={0,0,1,-1};
 22 int dy[]={1,-1,0,0};
 23 int n,m;
 24 
 25 struct MC{
 26     bool graph[N][N];
 27     int stk[N][N],dp[N],mc;
 28     int choice[N],vertex[N];
 29     void dfs(int n,int sz,int dep){
 30         if (sz==0){
 31             if (dep>mc){
 32                 mc=dep;
 33                 for (int i=0;i<mc;i++)
 34                     vertex[i]=choice[i];
 35             }
 36             return;
 37         }
 38         for (int i=0;i<sz;i++){
 39             int u=stk[dep][i];
 40             if (dep+dp[u]<=mc) return;
 41             if (dep+sz-i<=mc) return;
 42             choice[dep]=u;
 43             int cnt=0;
 44             for (int j=i+1;j<sz;j++){
 45                 int v=stk[dep][j];
 46                 if (graph[u][v])
 47                     stk[dep+1][cnt++]=v;
 48             }
 49             dfs(n,cnt,dep+1);
 50         }
 51     }
 52     int maxClique(int n){
 53         mc=1;
 54         //节点从1开始标号
 55         dp[n]=1;
 56         for (int i=n-1;i>=1;i--){
 57             int sz=0;
 58             for (int j=i+1;j<=n;j++)
 59                 if (graph[i][j])
 60                     stk[1][sz++]=j;
 61             choice[0]=i;
 62             dfs(n,sz,1);
 63             dp[i]=mc;
 64         }
 65         return mc;
 66     }
 67     void solve(int &cas) {
 68         map<char,int> mp;
 69         int cnt=0;
 70         for (int i=1;i<=n;i++) {
 71             for (int j=1;j<=m;j++) {
 72                 if (s[i][j]==‘.‘)
 73                     id[i][j]=++cnt;
 74                 else if (mp.find(s[i][j])==mp.end())
 75                     id[i][j]=mp[s[i][j]]=++cnt;
 76                 else
 77                     id[i][j]=mp[s[i][j]];
 78             }
 79         }
 80         //for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) cout<<id[i][j]<<" ";cout<<endl;
 81         for (int i=1;i<=cnt;i++) {
 82             for (int j=1;j<=cnt;j++) {
 83                 if (i==j) graph[i][j]=false;
 84                 graph[i][j]=true;
 85             }
 86         }
 87         for (int i=1;i<=n;i++) {
 88             for (int j=1;j<=m;j++) {
 89                 int u=id[i][j];
 90                 for (int k=0;k<4;k++) {
 91                     int ni=i+dx[k];
 92                     int nj=j+dy[k];
 93                     if (ni<=0||nj<=0||ni>n||nj>m) continue;
 94                     int v=id[ni][nj];
 95                     graph[u][v]=false;
 96                     graph[v][u]=false;
 97                 }
 98             }
 99         }
100         printf("Case #%d: %d\n",cas,maxClique(cnt));
101     }
102 }mc;
103 
104 int main () {
105     //freopen("out.txt","r",stdin);
106     int T;
107     scanf("%d",&T);
108     while (T--) {
109         scanf("%d %d",&n,&m);
110         for (int i=1;i<=n;i++) {
111             scanf("%s",s[i]+1);
112         }
113         static int cas=1;
114         mc.solve(cas);
115         cas++;
116     }
117     return 0;
118 }