Fire Net ZOJ - 1002

题意：

一个n * n 的棋盘 上面有些障碍物  放棋子 棋子不能在同一行 同一列 但可以在同一行或同一列隔着障碍物放

这题与poj1321  的思想差不多

对于一个位置 有两种状态放还是不放

参数inx  从1到n*n递增  inx/n表示x轴坐标   inx%n表示y轴坐标

k 为当前所用的棋子

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#define mem(a,b) memset(a,b,sizeof(a))

using namespace std;

const int maxn = , INF = 0xfffffff;

typedef long long LL;

char str[maxn][maxn];

int vis[maxn][maxn];

int n, minn;

int check(int x,int y)

{

    for(int i=x-; i>=; --i)

    {

        if(vis[i][y])

            return ;

        if(str[i][y] == 'X')

            break;

    }

    for(int i=y-; i>=; --i)

    {

        if(vis[x][i])

            return ;

        if(str[x][i] == 'X')

            break;

    }

    return ;

}

void dfs(int inx, int k)

{

    if(inx == n*n)

    {

        minn = max(k, minn);

        return;

    }

    int x = inx / n;

    int y = inx % n;

    if(str[x][y] == '.' && check(x,y))

    {

        vis[x][y] = ;

        dfs(inx+, k+);

        vis[x][y] = ;

    }

    dfs(inx+, k);

}

int main()

{

    while(cin>>n && n)

    {

        minn = -INF;

        mem(vis,);

        mem(str,);

        for(int i=;i<n;i++)

            cin>>str[i];

        dfs(,);

        cout<<minn<<endl;

    }

    return ;

}