搜索小练#1

Posted on Edited on In

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <cstdio>
#include <iostream>
#include <cstring>
#define INF 214474444
using namespace std;

int n, k, tot, stp;
int a[10][10], vis[10];
char s[10];

inline void dfs (int x) {
    if (stp == k) {
        ++ tot;
        return;
    }
    if (x > n) return;
    for (int i = 1; i <= n; ++ i)
        if (!vis[i] && a[x][i] == 1) {
            vis[i] = 1, ++ stp;
            dfs (x+1);
            vis[i] = 0, -- stp;
        }
    dfs (x+1);
}

int main () {
    while (cin >> n >> k) {
        if (n == -1 && k == -1) break;
        tot = stp = 0;
        memset (vis, 0, sizeof vis);
        memset (a, 0, sizeof a);
        for (int i = 1; i <= n; ++ i) {
            scanf ("%s", s+1);
            for (int j = 1; j <= n; ++ j) s[j] == '#' ? a[i][j] = 1 : a[i][j] = 0;
        }
        dfs (1);
        cout << tot << '\n';
    }
    return 0;
}
/*
2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1
*/

PS:

1.\(dfs\)参数只可以有一个

2.\(vis\)记录每一列是否有棋子放置

时隔两年，重新做了一下，题目不算难，但是有一个小细节没注意到，就是搜索的时候，不允许在之前找过的行中重新找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int n, k, tot;
int a[10][10], vis[10][10];
char c[10];

inline bool pd(int x, int y)
{
    int i, j;
    for (j = 1; j <= n; ++ j) if (a[x][j] == 1 && vis[x][j]) return false;
    for (i = 1; i <= n; ++ i) if (a[i][y] == 1 && vis[i][y]) return false;
    return true;
}

inline void dfs(int t, int x)
{
	if (x > k)
	{
		++ tot;
		//cout << "循环边界tot-->" << tot << '\n';
		return;
	}
	int i, j;
	for (i = t; i <= n; ++ i)
	{
		for (j = 1; j <= n; ++ j)
		{
			if (a[i][j] == 1 && ! vis[i][j] && pd(i, j))
			{
				vis[i][j] = 1;
				/*
				cout << "put this i--> " << i << ' ' << "j -->" << j << '\n';
				cout << "now_tot-->" << tot << '\n';
				cout << "接下来dfs--->" << x + 1 << '\n';
				*/
				dfs(i + 1, x + 1);
				vis[i][j] = 0;
			}
		}
	}
	return;
}

signed main()
{
	while (1)
	{
		int i, j; scanf ("%d%d", &n, &k);
		if (n == -1 && k == -1) return 0;
		memset(a, 0, sizeof a), tot = 0;
		memset(vis, 0, sizeof vis);
		for (i = 1; i <= n; ++ i)
		{
			scanf ("%s", c + 1);
			for (j = 1; j <= n; ++ j) a[i][j] = c[j] == '#' ? 1 : -1;
		}
		dfs(1, 1);
		cout << tot << '\n';
	}
	return 0;
}
/*
2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1
*/