ZOJ1002Fire Net
深度加回溯，类似于八皇后问题。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
char mp[6][6];//map
int len;//map length
int mb;//bigesst
int mbt;//now road length
int CP(int x, int y)//canput
{
    int i;
    i = y - 1;
    while(i >= 0 && mp[x][i] != 'X')
    {
        if(mp[x][i] == 'O')
            return 0;
        i--;
    }
    i = y + 1;
    while(i < len && mp[x][i] != 'X')
    {
        if(mp[x][i] == 'O')
            return 0;
        i++;
    }
    i = x - 1;
    while(i >= 0 && mp[i][y] != 'X')
    {
        if(mp[i][y] == 'O')
            return 0;
        i--;
    }
    i = x + 1;
    while(i < len && mp[i][y] != 'X')
    {
        if(mp[i][y] == 'O')
            return 0;
        i++;
    }
    return 1;
}
void DFS(int n)
{
    int i, j;
    int x, y;
    if(n == len * len)    
    {
        if(mb < mbt)
            mb = mbt;    
        return ;
    }
    x = n / len;
    y = n % len;
    if(mp[x][y] == '.' && CP(x, y))
    {
        mp[x][y] = 'O';
        mbt++;
        DFS(n + 1);
        mbt--;
        mp[x][y] = '.';
        
        DFS(n + 1);
    }
    else 
        DFS(n + 1);
}
int main()
{
    int i, j;
    scanf("%d", &len);
    getchar();
    while(len != 0)
    {
        for(i = 0; i < len; i++)//read map
            gets(mp[i]);
        mbt = mb = 0;
        DFS(0);

        printf("%d\n", mb);
        scanf("%d", &len);
        getchar();
    }
}
这道题跟之前走迷宫的题略有不同，走迷宫时起始点确定，当前点可走的方向确定。而这道题结束条件是判断过的格数超过总格数。
即使是合法的点也可以选择不放炮台。
posted on 2012-03-08 23:34 小鼠标 阅读(206) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2012年2月>
日一二三四五六
2930311234
567891011
12131415161718
19202122232425
26272829123
45678910

常用链接

随笔分类(111)

随笔档案(127)

friends

最新评论

  • 1. re: 线段树
  • 是这个样子的，所以在OJ有时候“卡住”了也不要太灰心，没准真的不是自己的原因呢。
    加油，祝你好运啦！
  • --小鼠标
  • 2. re: 线段树
  • 对于编程竞赛来说，Java所需时间一般为C/C++的两倍。合理的竞赛给Java的时间限制是给C/C++的两倍。
  • --伤心的笔
  • 3. re: poj1273--网络流
  • 过来看看你。
  • --achiberx
  • 4. re: （转）ubuntu11.10无法启动无线网络的解决方法
  • 膜拜大神。。查了一个下午资料终于在这里解决了问题。。神牛说的区域赛难道是ACM区域赛。。？
  • --Hang
  • 5. re: 快速排序、线性时间选择
  • 博主，谢谢你的文章。你的方法可以很好的处理分区基准在数组中重复的情况，书上的方法遇到这种输入会堆栈溢出。书上给出了解释但给的方法貌似不简洁。
  • --lsxqw2004

阅读排行榜