[kuangbin带你飞]专题一 简单搜索 - A - 棋盘问题

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<string>
 4 #include<vector>
 5 #include<cstring>
 6 using namespace std;
 7 struct node
 8 {
 9     int x;
10     int y;
11 };
12 int n, k, l, ans;
13 bool w[10], h[10];
14 vector<node>dot;
15 void bfs(int a, int b)
16 {
17     if(a==k+1)
18     {
19         ans++;
20         return;
21     }
22     for(int i = b; i < l; i++)
23     {
24         if(w[dot[i].x] || h[dot[i].y])    continue;
25         else
26         {
27             w[dot[i].x] = h[dot[i].y] = true;
28             bfs(a+1, i+1);
29             w[dot[i].x] = h[dot[i].y] = false;
30         }
31     }
32     return;
33 }
34 int main()
35 {
36 //    freopen("in.in","r",stdin);
37     string c;
38     node tmp;
39     while(cin>>n>>k)
40     {
41         dot.clear();
42         memset(w,0,sizeof(w));
43         memset(h,0,sizeof(h));
44         if(n==-1)    break;
45         for(int i = 1; i <= n; i++)
46         {
47             cin>>c;
48             for(int j = 1; j <= n; j++)
49             {
50                 
51                 if(c[j-1]==‘#‘)
52                 {
53                     tmp.x = i;
54                     tmp.y = j;
55                     dot.push_back(tmp);
56                 }
57             }            
58         }
59 
60         l = dot.size();
61         ans = 0;
62         bfs(1,0);
63         cout<<ans<<endl;
64     }
65     return 0;
66 }