1405 fire net.cpp

来自「威士忌的HDU题解.大概有260多题的源码。对于学习非常有好处。」· C++ 代码 · 共 68 行

#include <cstdio> 
using namespace std; 
char map[4][4]; 
int n,max; 

inline bool isOK(int i,int j) 
{ 
    int k; 
     
    for(k=i;k<n;k++) 
        if(map[k][j]=='X') 
            break; 
        else if(map[k][j]!='.') 
            return false; 
    for(k=i;k>=0;k--) 
        if(map[k][j]=='X') 
            break; 
        else if(map[k][j]!='.') 
            return false; 
    for(k=j;k<n;k++) 
        if(map[i][k]=='X') 
            break; 
        else if(map[i][k]!='.') 
            return false; 
    for(k=j;k>=0;k--) 
        if(map[i][k]=='X') 
            break; 
        else if(map[i][k]!='.') 
            return false; 
    return true; 
} 
int dfs(int step) 
{ 
    int i,j,k; 
     
    max= step > max ? step:max; 
         
    for(i=0;i<n;i++) 
        for(j=0;j<n;j++) 
        { 
            if(map[i][j]=='.' && isOK(i,j)) 
            { 
                map[i][j]=step; 
                dfs(step+1); 
                map[i][j]='.'; 
            } 
        } 
    return max; 
} 

int main() 
{ 
    int i,j;
    char ch; 

    while(scanf("%d",&n)==1 && n!=0) 
    {
        getchar(); 
        for(i=0;i<n;i++) 
            gets(map[i]); 
        max=0; 
        dfs(0); 
        printf("%d\n",max); 
    } 
    return 0; 
}