pku 1321

2009年8月9日

题目链接：PKU 1321 棋盘问题

分类：DFS

题目分析与算法原型
        一道简单搜索题，没什么特别好说的，dfs(int hang,int leave),hang和leave分别表示现在要放入的行号以及还剩的棋子个数，枚举每行能放的列，依次放入再调用dfs()即可.........

 
Code:

 1#include<stdio.h>
 2#include<string.h>
 3#define max 10
 4int n,k,row,count;
 5char map[max][max];
 6bool hang[max],lie[max];
 7void dfs(int row,int leave)
 8{
 9    int j;
10    if(leave==0)
11    {
12        count++;
13        return;
14    }
15    if(row>=n)return;
16    for(j=0;j<n;j++)
17    {
18        if(!lie[j]&&map[row][j]=='#')
19        {
20            lie[j]=true;
21            dfs(row+1,leave-1);
22            lie[j]=false;
23            
24        }
25    }
26    dfs(row+1,leave);
27}
28int main()
29{
30    int i;
31    while(scanf("%d%d",&n,&k)!=EOF)
32    {
33        if(n==-1&&k==-1)break;
34        memset(lie,false,sizeof(lie));
35        for(i=0;i<n;i++)scanf("%s",map[i]);
36        count=0;
37        dfs(0,k);
38        printf("%d\n",count);
39    }
40    return 1;
41}

posted on 2009-08-09 13:45 蜗牛也Coding 阅读(182) 评论(0)  编辑 收藏 引用


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


<2009年8月>
日一二三四五六
2627282930311
2345678
9101112131415
16171819202122
23242526272829
303112345

导航

统计

常用链接

留言簿(8)

随笔档案(78)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜