简单的dfs题 --- POJ1321 棋盘问题

题目链接：

http://poj.org/problem?id=1321

题目大意：

你有k个棋子，若干个可以填的位置，要求填下一个棋子后其行和列不能填棋子。

思路：

dfs策略

画图理解更好些：

填下一个棋子。行列需要跳一下，dfs的时候for循环代表行，用一个vis数组来表示该列能否用，如果符合条件的需要i+1跳到下一行。

所以for循环第一个可以这样写：

for(int i = x; i < n; ++i)

下面由于用了vis数组，所以从0开始遍历就好。

下面是AC代码：

#include <iostream>
#include <cstdio>
#include <string.h>

using namespace std;
const int MX = 100+5;

char mp[MX][MX];
int vis[MX];
int n, k, ans;

void dfs(int x, int y)
{
    if(y >= k)
    {
        ans++;
        return;
    }
    for(int i = x; i < n; ++i)
        for(int j = 0; j < n; ++j)
        {
            if(mp[i][j] == '#' && !vis[j])
            {
                vis[j] = 1;
                dfs(i+1, y+1);
                vis[j] = 0; //回溯， 类似n皇后问题。
            }
        }
    return;
}

int main()
{
    while(scanf("%d%d", &n, &k) != EOF && ((n!=-1)&&(k!=-1)))
    {
        ans = 0;
        memset(mp, 0, sizeof(mp));
        memset(vis, 0, sizeof(vis));
        for(int i = 0; i < n; ++i) scanf("%s", mp[i]);
        dfs(0, 0);
        printf("%d
", ans);
    }
}

如有疑问，欢迎评论指出！