ZOJ 1002 -- Fire Net

开始刷ZOJ，希望能有一个新的开始，新的机会
题意 : 大致就是一个矩阵模型，X为墙，保证每个人都不能相互看到，求这种情况下的可以最多加入的人的个数
题解 : 大致推算出复杂度，暴力解决问题

/*  
 * 2019/11/21 * 因为N最大为4，所以可以枚举所有情况，复杂度为2^（N*N）  
 * 暴力求解  
 */
#include <cstdio>  
#include <cstring>  
using namespace std;  
const int MAXN = 5;  
char s[MAXN][MAXN];  
int t[MAXN][MAXN];  
int N;  
int max(int a,int b){  
    return a>b?a:b;  
}  
int row(int x,int y){  
    for(int i=x+1;i<N;i++){  
        if(s[i][y]=='X')break;  
 if(t[i][y])return 0;  
  }  
    for(int i=x-1;i>=0;i--){  
        if(s[i][y]=='X')break;  
 if(t[i][y])return 0;  
  }  
    return 1;  
}  
int cloumn(int x,int y){  
    for(int i=y+1;i<N;i++){  
        if(s[x][i]=='X')break;  
 if(t[x][i])return 0;  
  }  
    for(int i=y-1;i>=0;i--){  
        if(s[x][i]=='X')break;  
 if(t[x][i])return 0;  
  }  
    return 1;  
}  
int slove(int M){  
    int cnt=0;  
 for(int i=0;i<N;i++){  
        for(int j=0;j<N;j++){  
            cnt+=M%2;  
  t[i][j]=M%2;  
  M/=2;  
 if(t[i][j]&&s[i][j]=='X')return 0;  
  }  
    }  
//    for(int i=0;i<N;i++){  
//        for(int j=0;j<N;j++){  
//            printf("%d ",t[i][j]);  
//        }  
//        printf("\n");  
//    }  
  for(int i=0;i<N;i++){  
        for(int j=0;j<N;j++){  
            if(t[i][j]){  
                if(row(i,j)&&cloumn(i,j));  
 else return 0;  
  }  
        }  
    }  
    return cnt;  
}  
int main(){  
    while(scanf("%d",&N)!=EOF&&N){  
        int maxx=0;  
 for(int i=0;i<N;i++)  
            scanf("%s",s[i]);  
//        for(int i=0;i<N;i++)  
//            printf("%s\n",s[i]);  
  for(int i=0;i<1<<(N*N);i++){  
            memset(t,0,sizeof(t));  
  maxx=max(maxx,slove(i));  
  }  
        printf("%d\n",maxx);  
  }  
    return 0;  
}

ZOJ 1002 -- Fire Net

原文：https://www.cnblogs.com/Vagrant-ac/p/11908536.html