最新消息:点击查看大S的省钱秘笈

POJ 1321 棋盘问题 C语言版

POJ题解 Slyar 2662浏览 2评论

文章作者:姜南(Slyar) 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。

Description

在一个给定形状的棋盘(形状可能是不规则的)上面摆放棋子,棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列,请编程求解对于给定形状和大小的棋盘,摆放k个棋子的所有可行的摆放方案C。

Input

输入含有多组测试数据。
每组数据的第一行是两个正整数,n k,用一个空格隔开,表示了将在一个n*n的矩阵内描述棋盘,以及摆放棋子的数目。 n <= 8 , k <= n
当为-1 -1时表示输入结束。
随后的n行描述了棋盘的形状:每行有n个字符,其中 # 表示棋盘区域, . 表示空白区域(数据保证不出现多余的空白行或者空白列)。

Output

对于每一组数据,给出一行输出,输出摆放的方案数目C (数据保证C<2^31)。

Sample Input

2 1
#.
.#
4 4
…#
..#.
.#..
#…
-1 -1

Sample Output

2
1

Slyar:类似八皇后的一道题,DFS+回溯。每次标记当前棋子所在列为不可放,然后搜索下一行即可,回溯时将当前列恢复为可放置,可以省掉每次初始化标记数组。我是47MS过的,据说有人用什么”棋盘多项式”可以0MS过,不过我不会,嘎嘎…

#include 
#include 
#include 

#define MAX 9

int n, k, sum, sumk;
char map[MAX][MAX];
int visit[100] = {0};

void dfs(int a, int b)
{
    int i, j;
    if (sumk == k)
    {
        sum++;
        return;
    }
    /* 置当前列不可放 */
    visit[b] = 1;
    /* 从下一行开始搜索 */
    for (i = a + 1; i <= n; i++)
    {
        /* 每一行从左向右搜索 */
        for (j = 1; j <= n; j++)
        {
            if (map[i][j] == '#' && visit[j] == 0)
            {
                /* 格子可放棋子数 + 1 */
                sumk++;
                /* 继续向下搜索 */
                dfs(i, j);
                /* 回溯时棋子数 - 1 */
                sumk--;
            }
        }
    }
    /* 回溯时重置列可放 */
    visit[b] = 0;
}

int main()
{
    int i, j;
    while(1)
    {
        scanf("%d%d", &n, &k);
        if(n == -1 && k == -1) break;
        sum = 0;
        for (i = 1; i <= n; i++)
        {
            getchar();
            for(j = 1; j <= n; j++)
            {
                scanf("%c", &map[i][j]);
            }
        }
        for (i = 1; i <= n; i++)
        {
            for(j = 1; j <= n; j++)
            {
                if (map[i][j] == '#')
                {
                    sumk = 1;
                    dfs(i,j);
                }
            }
        }
        printf("%d\n", sum);
    }
    //system("pause");
    return 0;
}

转载请注明:Slyar Home » POJ 1321 棋盘问题 C语言版

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

网友最新评论 (2)

  1. @Felix021, 像Djk、floyd、KMP等我现在都看不懂...悲剧... 能干嘛?=_=
    Slyar12年前 (2009-04-18)回复
  2. 开始刷POJ了,NB。 POJ我才过了几道题,界面太难看,不喜欢去。 不过今天为了项目的东东要回头看看KMP,头疼。 ------ p.s. 推荐一下中国移动的139信箱,免费的邮件推送服务阿,超赞~~
    Felix02112年前 (2009-04-18)回复