zju 1002.cpp

zju 1002 Fire Net 代码

#include <cstdio>
#include <iostream>
using namespace std;
char map[5][5];
int n;
int mmax;
void init()
{
    int i, j;
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
        {
            cin >> map[i][j];
        }
    }
}

int Putcan(int col, int row)
{
    int i, j;
    for (i = row - 1; i >= 0; i--)
    {
        if (map[col][i] == '0')
            return 0;
        else if (map[col][i] == 'X')
            break;
    }
    for (j = col - 1; j >= 0; j--)
    {
        if (map[j][row] == '0')
            return 0;
        else if (map[j][row] == 'X')
            break;
    }
    return 1;
}

void Slove(int pos, int ccount)
{
    int col, row;
    if (pos == n *n)
    {
        if (mmax < ccount)
            mmax = ccount;
        return ;
    }
    col = pos / n;
    row = pos % n;
    if (map[col][row] == '.' && Putcan(col, row))
    {
        map[col][row] = '0';
        Slove(pos + 1, ccount + 1);
        map[col][row] = '.';
    }
    Slove(pos + 1, ccount);
}

int main()
{
    while (cin >> n && n)
    {
        mmax = 0;
        init();
        Slove(0, 0);
        printf("%d\n", mmax);
    }
    return 0;
}