Fire Net HDU 1045

简单深搜,可以完全暴力,不会超时的。

Fire Net  HDU  1045
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
#define MAX(a,b) (a>b?a:b) 
char maze[10][10];
int n, maxn;

void DFS(int step,int count);
int cheak(int x, int y);
int main()
{
    int i;
    while(scanf("%d",&n), n)
    {
        maxn = 0;
        for(i = 0; i < n; i++)
            scanf("%s",maze[i]);
        DFS(0,0);
        printf("%d\n",maxn);
    }
    return 0;
}

void DFS(int step,int count)
{
    int x, y;
    maxn = MAX(maxn,count);
    if(step == n*n)
        return ;
    x = step/n;
    y = step%n;
    if(maze[x][y] == . && cheak(x,y))
    {
        maze[x][y] = O;
        DFS(step+1,count+1);
        maze[x][y] = .;
    }
    DFS(step + 1, count);
}

int cheak(int x, int y)
{
    int i;
    for(i = x-1; i >= 0; i--)
    {
        if(maze[i][y] == O)
            return 0;
        else if(maze[i][y] == X)
            break;
    }
    for(i = y-1; i >= 0; i--)
    {
        if(maze[x][i] == O)
            return 0;
        else if(maze[x][i] == X)
            break;
    }
    return 1;
}
Fire Net  HDU  1045

 

Fire Net HDU 1045,布布扣,bubuko.com

Fire Net HDU 1045

上一篇:Js中的this关键字


下一篇:PHP数组