每次range标记一行中一个#，没有在同列的 ,并dfs下一行

#include <iostream>
#include <string>
using namespace std;

int cnt = 0; 
void dfs(string* grid, int& n, int k, int i, int range)
{ 
    if (!k)
    {
        cnt++;
        return;
    }
    if (i == n)
        return;
    for(int j = 0; j < n; ++j)
        if (grid[i][j] == '#' && !((1 << j) & range)) 
            dfs(grid, n, k - 1, i + 1, (1 << j) | range); 
}

void calc(string* grid, int& n, int& k)
{
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
        {
            if (grid[i][j] == '#')
            {
                int range = 1 << j;
                dfs(grid, n, k - 1, i + 1, range);
                for(int t = i + 2; t < n; ++t)
                    dfs(grid, n, k - 1, t, range);
            }
        }
}
int main()
{
    int n, k;
    while(scanf("%d%d", &n, &k) , n != -1 && k != -1)
    {
        string *grid = new string[n];
        for(int i = 0; i < n; ++i)
            cin >> grid[i];
        cnt = 0;
        calc(grid, n, k);
        cout << cnt << endl;
        delete[] grid;
    }
    return 0;
}

• Re: 样例 (241) 3074583 2010-08-03 18:20:46
  • Re: 样例 (10) wentianxiaokai 2010-08-07 21:03:45
    • Re: 样例 (41) shuyezi 2011-07-18 21:24:27
      • Re: 样例 (4) jrf 2012-09-24 13:50:59
      • 不是11而是8吧，你怎么数出11的 (2) Belldandy 2013-11-16 20:20:32