hdu 1045 FireNet

テーマリンク:http://acm.hdu.edu.cn/showproblem.php?pid=1045
筋:一行一行の検索で、今は「X」なら次を探して、もし現在は「.」なら、装置を置くことができるかどうかを判断します.できないなら、直接に次を検索してもいいです.できれば、二つの状況に分けて、一つは置いてもいいです.
コード(長いですが、分かりやすいです):

#include <cstdio>
#include <cstring>

char s[10][10];
int n;
int v[10][10];
int ans;

bool isLegal(int x,int y)

{
    bool north = true;
    bool south = true;
    bool east = true;
    bool west = true;
    for(int i = x - 1; i >= 0 && s[i][y] != 'X'; --i)
        if(v[i][y])
        {
            north = false;
            break;
        }
    for(int i = x + 1; i < n && s[i][y] != 'X'; ++i)
        if(v[i][y])
        {
            south = false;
            break;
        }
    for(int i = y + 1; i < n && s[x][i] != 'X'; ++i)
        if(v[x][i])
        {
            east = false;
            break;
        }
    for(int i = y - 1; i >= 0 && s[x][i] != 'X'; --i)
        if(v[x][i])
        {
            west = false;
            break;
        }
    if(north && south && east && west)
        return true;
    return false;
}
void dfs(int x,int y,int sum)

{
    if(x == n && y == 0)
    {
        if(sum > ans)
            ans = sum;
        return ;
    }
    if(s[x][y] == 'X')
    {
        if(y == n - 1)
            dfs(x + 1,0,sum);
        else
            dfs(x,y + 1,sum);
    }
    if(s[x][y] == '.')
    {
        if(isLegal(x,y))
        {
            if(y == n - 1)
            {
                v[x][y] = 1;
                dfs(x + 1,0,sum + 1);  // 
                v[x][y] = 0;
                dfs(x + 1,0,sum);   //  
            }
            else
            {
                v[x][y] = 1;
                dfs(x,y + 1,sum + 1); // 
                v[x][y] = 0;
                dfs(x,y + 1,sum); //  
            }
        }
        else
        {
            if(y == n - 1)
                dfs(x + 1,0,sum);
            else
                dfs(x,y + 1,sum);
        }
    }
}
int main()

{
    while(~scanf("%d",&n),n)
    {
        memset(v,0,sizeof(v));
        for(int i = 0; i < n; ++i)
            scanf("%s",s[i]);
        ans = 0;
        dfs(0,0,0);
        printf("%d
",ans);
    }
    return 0;
}