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,古老的榕树,5-wow.com

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。