Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

求解~兄弟们的样例我都测试过了 就是WA!!帮我看看 这不知杯具到哪了...

Posted by 3074583 at 2010-08-03 18:01:52 on Problem 1321
每次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;
}


Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator