简单搜索练习

发表于 更新于 分类于 本文字数： 32k 阅读时长 ≈ 29 分钟

kuangbin专题和洛谷专题的刷题记录，以及简单搜索总结

知识点

  • BFS
  • DFS
  • 路径还原

白书例题（DFS + 简单剪枝）

给定整数a1、a2…、an，判断是否可以从中选出若干数，使他们的和恰好为k。

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
#include<iostream>
#include<algorithm>
using namespace std;

const int MAX_N = 20;

int n;
int a[MAX_N];
int k;

bool dfs(int i, int sum)
{
    if(sum > k) return false;//剪枝
    if(i == n) return sum == k;
    if(dfs(i+1, sum)) return true;
    if(dfs(i+1, sum+a[i])) return true;
    return false;
}

int main()
{
    cin >> n;
    for(int i=0; i<n; ++i)  cin >> a[i];
    cin >> k;
    if(dfs(0, 0))
        printf("yes\n");
    else
        printf("no\n");
    return 0;
}

POJ1321（DFS，八皇后变式）

类似n皇后问题，区别在于某行可不放棋子

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<cstring>

const int MAX_N = 8;

char map[MAX_N+1][MAX_N+1];
int n, k, ans = 0;
bool check[MAX_N+1];

void dfs(int x, int now)
{
    if(x == n && now != k)
        return ;
    if(now == k)
    {
        ans++;
        return ;
    }
    else
    {
        for(int i = 0; i < n; ++i)
        {
            if(map[x][i] == '#' && !check[i])
            {
                check[i] = 1;
                dfs(x+1, now+1);
                check[i] = 0;
            }
        }
        dfs(x+1, now);
    }
}

int main()
{
    while(true)
    {
        scanf("%d%d", &n, &k);
        if(n == -1 && k == -1)
            break;
        for(int i = 0; i < n; ++i)
        {
            scanf("%s", map[i]);
        }
        ans = 0;
        memset(check, 0, sizeof(check));
        dfs(0, 0);
        printf("%d\n", ans);
    }
    return 0;
}

POJ2251（三维BFS）

简单扩展下二维BFS，用结构体表示坐标即可

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include<cstdio>
#include<queue>
using namespace std;

struct Node
{
    int l;
    int r;
    int c;
};

const int MAX_LRC = 30 + 1;
const int INF = 1e9;

char maze[MAX_LRC][MAX_LRC][MAX_LRC];
int t[MAX_LRC][MAX_LRC][MAX_LRC];
int L, R, C;
int sl, sr, sc;
int el, er, ec;

int dl[] = {1, -1, 0, 0, 0, 0};
int dr[] = {0, 0, 1, -1, 0, 0};
int dc[] = {0, 0, 0, 0, 1, -1};

void bfs()
{
    queue<Node> que;
    Node q;
    q.l = sl;
    q.r = sr;
    q.c = sc;
    que.push(q);
    while(que.size())
    {
        Node qu = que.front();
        que.pop();
        for(int i = 0; i < 6; ++i)
        {
            Node qe;
            qe.l = qu.l + dl[i];
            qe.r = qu.r + dr[i];
            qe.c = qu.c + dc[i];
            if(qe.l >= 0 && qe.l < L && qe.r >= 0 && qe.r < R
                && qe.c >= 0 && qe.c < C && maze[qe.l][qe.r][qe.c] != '#'
                && t[qe.l][qe.r][qe.c] == INF)
            {
                que.push(qe);
                t[qe.l][qe.r][qe.c] = t[qu.l][qu.r][qu.c] + 1;
            }
        }
    }
}

int main()
{
    while(true)
    {
        scanf("%d%d%d", &L, &R, &C);
        if(L == 0)
            break;
        for(int i = 0; i < L; ++i)
        {
            for(int j = 0; j < R; ++j)
            {
                scanf("%s", maze[i][j]);
                for(int k = 0; k < C; ++k)
                {
                    t[i][j][k] = INF;
                    if(maze[i][j][k] == 'S')
                    {
                        sl = i;
                        sr = j;
                        sc = k;
                    }
                    else if(maze[i][j][k] == 'E')
                    {
                        el = i;
                        er = j;
                        ec = k;
                    }
                }
            }
        }
        t[sl][sr][sc] = 0;
        bfs();
        if(t[el][er][ec] == INF)
            printf("Trapped!\n");
        else
            printf("Escaped in %d minute(s).\n", t[el][er][ec]);
    }
    return 0;
}

POJ3278（非图类BFS）

其实这题就是步长不同的BFS

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
#include<cstdio>
#include<queue>
using namespace std;

const int MAX_N = 1e5 + 1;

int n, k;
int ans[MAX_N];

void bfs()
{
    queue<int> que;
    que.push(n);
    while(que.size())
    {
        int p = que.front();
        que.pop();
        if(p == k)
            break;
        for(int i = 0; i < 3; ++i)
        {
            int t;
            if(i == 0)
                t = p - 1;
            else if(i == 1)
                t = p + 1;
            else
                t = p * 2;
            if(t >= 0 && t <= MAX_N && !ans[t])
            {
                que.push(t);
                ans[t] = ans[p] + 1;
            }
        }
    }
}

int main()
{
    scanf("%d%d", &n, &k);
    bfs();
    printf("%d\n", ans[k]);
    return 0;
}

POJ3279（集合的整数表示 + 枚举）

感觉不像搜索……

需要枚举集合，用到集合的整数表示

第一行情况固定了，后面每一行的翻转情况也就确定了

我的方法比较傻，所以再贴一个白书上的题解

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include<cstdio>
#include<cstring>

const int MAX_N = 15 + 1;

int rec[MAX_N][MAX_N];
int rect[MAX_N][MAX_N];
int t[MAX_N][MAX_N];
int ans[MAX_N][MAX_N];
int dx[] = {1, 0, 0, -1, 0};
int dy[] = {0, 1, 0, 0, -1};

int N, M;

bool check(int x, int y) //检查是否合法
{
    return (0 <= x && x < M && 0 <= y && y < N);
}

void flip(int x, int y) //翻转上下左右和自己
{
    for(int i = 0; i < 5; ++i)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(check(nx, ny))
        {
            rect[nx][ny] = !rect[nx][ny];
        }
    }
}

int solve()
{
    for(int i = 1; i < M; ++i) //第二行开始
    {
        for(int j = 0; j < N; ++j)
        {
            if(rect[i - 1][j]) //如果上面一行的这列是黑的，则翻转
            {
                flip(i, j);
                t[i][j] = 1;
            }
        }
    }

    for(int j = 0; j < N; ++j)
    {
        if(rect[M - 1][j])
            return -1;
    }

    int res = 0;
    for(int i = 0; i < M; ++i)
    {
        for(int j = 0; j < N; ++j)
        {
            if(t[i][j])
                res += 1;
        }
    }
    return res;
}

int main()
{
    int res = -1;

    scanf("%d%d", &M, &N);
    for(int i = 0; i < M; ++i)
    {
        for(int j = 0; j < N; ++j)
        {
            scanf("%d", &rec[i][j]);
        }
    }

    for(int i = 0; i < 1 << N; ++i) //枚举每个子集,注意，最小字典序应从最右边一位枚举
    {
        memset(t, 0, sizeof(t));
        memcpy(rect, rec, sizeof(rec)); //建立副本
        for(int j = 0; j < N; ++j) //第一行的情况
        {
            t[0][N - 1 - j] = i >> j & 1; //i右移j个单位，那个位上的值
        }

        for(int k = 0; k < N; ++k) //翻转第一行
        {
            if(t[0][k])
                flip(0, k);
        }

        // for(int j = 0; j < M; ++j)
        // {
        //     for(int k = 0; k < N; ++k)
        //     {
        //         printf("%d ", rect[j][k]);
        //     }
        //     printf("\n");
        // }
        // printf("\n");

        int num = solve(); //根据第一行推断后面几行
        if(num >= 0 && (res < 0 || res > num))
        {
            res = num;
            memcpy(ans, t, sizeof(t));
        }
    }

    if(res == -1)
        printf("IMPOSSIBLE\n");
    else
    {
        for(int j = 0; j < M; ++j)
        {
            for(int k = 0; k < N; ++k)
            {
                printf("%d ", ans[j][k]);
            }
            printf("\n");
        }
    }
    return 0;
}
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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include<cstdio>
#include<cstring>

const int MAX_N = 15 + 1;
const int MAX_M = 15 + 1;
const int dx[5] = {-1, 0, 0, 0, 1};
const int dy[5] = {0, -1, 0, 1, 0};

int M, N;
int tile[MAX_M][MAX_N];

int opt[MAX_M][MAX_N];
int flip[MAX_M][MAX_N];

int get(int x, int y) //查询(x, y)颜色
{
    int c = tile[x][y];
    for(int d = 0; d < 5; ++d)
    {
        int x2 = x + dx[d];
        int y2 = y + dy[d];
        if(0 <= x2 && x2 < M && 0 <= y2 && y2 < N)
        {
            c += flip[x2][y2];
        }
    }
    return c % 2;
}

int calc() //求出第二行开始的翻转方法
{
    for(int i = 1; i < M; ++i) //若为黑，则翻转
    {
        for(int j = 0; j < N; ++j)
        {
            if(get(i - 1, j) != 0)
            {
                flip[i][j] = 1;
            }
        }
    }

    for(int j = 0; j < N; ++j) //判断最后一行是否全白
    {
        if(get(M - 1, j) != 0)
            return -1;
    }

    int res = 0;
    for(int i = 0; i < M; ++i) //统计次数
    {
        for(int j = 0; j < N; ++j)
        {
            res += flip[i][j];
        }
    }
    return res;
}

void solve()
{
    int res = -1;

    for(int i = 0; i < 1 << N; ++i)
    {
        memset(flip, 0, sizeof(flip));
        for(int j = 0; j < N; ++j)
        {
            flip[0][N - j - 1] = i >> j & 1;
        }

        int num = calc();
        if(num >= 0 && (res < 0 || res > num))
        {
            res = num;
            memcpy(opt, flip, sizeof(flip));
        }
    }

    if(res < 0)
    {
        printf("IMPOSSIBLE\n");
    }
    else
    {
        for(int i = 0; i < M; ++i)
        {
            for(int j = 0; j < N; ++j)
            {
                printf("%d%c", opt[i][j], j + 1 == N ? '\n' : ' ');
            }
        }
    }
}

int main()
{
    scanf("%d%d", &M, &N);
    for(int i = 0; i < M; ++i)
    {
        for(int j = 0; j < N; ++j)
        {
            scanf("%d", &tile[i][j]);
        }
    }
    solve();
    return 0;
}

POJ1426（BFS + 思考）

再字符串后分别加0和1，然后判断余数，若余数没有出现过，则是一个新状态，加入队列

可以用除法列竖式来理解算法思路

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
#include<cstdio>
#include<iostream>
#include<string>
#include<queue>
#include<cstring>
using namespace std;

int n;
int book[300];

struct node
{
    int y;
    string ans;
    node(int y, string ans) : y(y), ans(ans){}
};

void solve()
{
    queue<node> que;
    que.push(node(1, "1"));
    int yy; //新余数

    while(que.size())
    {
        node t = que.front();
        que.pop();

        if(!t.y) //如果余数是0，则输出
        {
            cout << t.ans << '\n';
            return ;
        }

        yy = (t.y * 10 + 1) % n; //末尾加1的情况
        if(!book[yy])
        {
            book[yy] = 1;
            que.push(node(yy, t.ans + "1")); //记录路径
        }

        yy = (t.y * 10) % n; //末尾加0的情况
        if(!book[yy])
        {
            book[yy] = 1;
            que.push(node(yy, t.ans + "0"));
        }
    }
}

int main()
{
    while(true)
    {
        scanf("%d", &n);
        if(!n) break;
        memset(book, 0, sizeof(book));
        solve();
    }
    return 0;
}

POJ3126（素数筛 + 非图类BFS）

枚举改变一个数字后的所有状态，判断是否是素数，是素数则放入队列

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;

const int MAX_N = 10000;

bool prime[MAX_N];
int d[MAX_N];

void init()
{
    for(int i = 1; i <= 9999; ++i)
    {
        prime[i] = true;
    }
    prime[1] = false;
}

void prim()
{
    init();
    for(int i = 2; i <= 9999; ++i)
    {
        if(prime[i])
        {
            for(int j = 2; j * i <= 9999; ++j)
            {
                prime[j * i] = false;
            }
        }
    }
}

int n;
int a, b;

int solve(int a, int b)
{
    if(a == b)
        return 0;
    queue<int> que;
    que.push(a);
    d[a] = 0;
    while(que.size())
    {
        int t = que.front();
        que.pop();
        int temp = t / 1000;
        for(int i = 1; i < 10; ++i)
        {
            if(i == temp)
                continue;
            int t1 = i * 1000 + t - temp * 1000;
            if(prime[t1] && d[t1] == -1)
            {
                d[t1] = d[t] + 1;
                que.push(t1);
            }
        }
        temp = t % 1000 / 100;
        for(int i = 0; i < 10; ++i)
        {
            if(i == temp)
                continue;
            int t1 = i * 100 + t - temp * 100;
            if(prime[t1] && d[t1] == -1)
            {
                d[t1] = d[t] + 1;
                que.push(t1);
            }
        }
        temp = t % 100 / 10;
        for(int i = 0; i < 10; ++i)
        {
            if(i == temp)
                continue;
            int t1 = i * 10 + t - temp * 10;
            if(prime[t1] && d[t1] == -1)
            {
                d[t1] = d[t] + 1;
                que.push(t1);
            }
        }
        temp = t % 10;
        for(int i = 0; i < 10; ++i)
        {
            if(i == temp )
                continue;
            int t1 = t - temp + i;
            if(prime[t1] && d[t1] == -1)
            {
                d[t1] = d[t] + 1;
                que.push(t1);
            }
        }
    }
    return d[b];
}

int main()
{
    prim(); //筛素数
    scanf("%d", &n);
    for(int i = 0; i < n; ++i)
    {
        scanf("%d%d", &a, &b);
        fill(d, d + MAX_N, -1);
        int ans = solve(a, b);
        if(ans == -1)
            printf("Impossible\n");
        else
            printf("%d\n", ans);
    }
    return 0;
}

POJ3087（打表 + 模拟？）

我已经想到一个绝妙的证明，可惜这里空间太小写不下（皮）

是道模拟题吧，不知道为什么归在搜索。编写很简单，但是证明了一个多小时还证不出来，题解也没有相关证明。

设a1,a2,…a2n

则新串b1,b2,…b2n

有bi =a (i & 1 ? i = (i + 1) / 2 : i / 2);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<cstdio>

int main()
{
    int n;
    n = 10;
    int i = 2;
    while(true)
    {
        if(i & 1)
            i = (i + 1) / 2 + n; //新i
        else
            i = i / 2; //新i
        printf("%d\n", i);
    }
    return 0;
}

打表发现总有一个新i会等于旧i，也就是说，总会有bi = … = ai，

用反证法。设i0，i的范围为(0,2n]，如果i0经过2n次变换，ik始终不等于i0，那么必定有个i出现了两次，而这个i一定由i0变化而来，所以i0 在变化中出现了循环，也即在2n次变换中，一定存在bi = … = ai。

但是思路有点问题，bi = … = ai所用的次数各不相同，无法证明所有的b和a相等……

看看学了离散和具体数学后有没有办法证明吧。

AC代码

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
//不严谨，待证明

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

string str[1000];
int t;
int len;
string str1, str2, str3;

bool find(string strn, int sum)
{
    for(int i = 0; i < sum; ++i)
    {
        if(str[i] == strn)
            return true;
    }
    return false;
}

int main()
{
    cin >> t;
    for(int i = 0; i < t; ++i)
    {
        cin >> len;
        cin >> str1 >> str2 >> str3;
        int sum = 0; //新字串的数量
        while(true)
        {
            string strt = str3;
            for(int j = 0; j < len; ++j)
            {
                strt[j*2] = str2[j];
                strt[j*2+1] = str1[j];
            }
            str[sum] = strt;
            if(str[sum] == str3)
            {
                cout << i+1 << ' ' << sum+1 << '\n';
                break;
            }
            else if(find(str[sum], sum))
            {
                cout << i+1 << ' ' << -1 << '\n';
                break;
            }
            sum++;
            for(int j = 0; j < len; ++j)
            {
                str1[j] = strt[j];
                str2[j] = strt[len + j];
            }
        }
    }
    return 0;
}

POJ3414（BFS + 思考）

参考自博客https://blog.csdn.net/qq_41280600/article/details/102491233

新思路，变量结构体中一个值储存路径

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
//新思路，bfs中，用变量记录每条路径
//https://blog.csdn.net/qq_41280600/article/details/102491233
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<queue>
using namespace std;

struct node //初始化顺序要对应，不然会warning
{
    int a, b;
    string opt;
    int step;
    node(int a, int b, string opt, int step): a(a), b(b), opt(opt), step(step){}
};

int a, b, c;
int vis[105][105];

string bfs()
{
    queue<node> que;
    que.push(node(0, 0, "", 0));
    vis[0][0] = 1;

    while(que.size())
    {
        node t = que.front();
        que.pop();
        if(t.a == c || t.b == c)
        {
            cout << t.step <<endl; //输出步数
            return t.opt; //返回路径
        }

        /* Fill */
        if(!vis[a][t.b])
        {
            vis[a][t.b] = 1;
            que.push(node(a, t.b, t.opt + "FILL(1)\n", t.step + 1));
        }
        if(!vis[t.a][b])
        {
            vis[t.a][b] = 1;
            que.push(node(t.a, b, t.opt + "FILL(2)\n", t.step + 1));
        }

        /* DROP */
        if(t.a != 0 && !vis[0][t.b])
        {
            vis[0][t.b] = 1;
            que.push(node(0, t.b, t.opt + "DROP(1)\n", t.step + 1));
        }
        if(t.b != 0 && !vis[t.a][0])
        {
            vis[t.a][0] = 1;
            que.push(node(t.a, 0, t.opt + "DROP(2)\n", t.step + 1));
        }

        /* POUR */
        if(t.a != 0 && t.b != b)
        {
            if(t.a + t.b <= b)
            {
                if(!vis[0][t.a + t.b])
                {
                    vis[0][t.a + t.b] = 1;
                    que.push(node(0, t.a + t.b, t.opt + "POUR(1,2)\n", t.step + 1));
                }
            }
            else
            {
                if(!vis[t.a + t.b - b][b])
                {
                    vis[t.a + t.b - b][b] = 1;
                    que.push(node(t.a + t.b - b, b, t.opt + "POUR(1,2)\n", t.step + 1));
                }
            }
        }
        if(t.b != 0 && t.a != a)
        {
            if(t.a + t.b <= a)
            {
                if(!vis[t.a + t.b][0])
                {
                    vis[t.a + t.b][0] = 1;
                    que.push(node(t.a + t.b, 0, t.opt + "POUR(2,1)\n", t.step + 1));
                }
            }
            else
            {
                if(!vis[a][t.a + t.b - a])
                {
                    vis[a][t.a + t.b - a] = 1;
                    que.push(node(a, t.a + t.b - a, t.opt + "POUR(2,1)\n", t.step + 1));
                }
            }
        }
    }
    return "impossible";
}

int main()
{
    scanf("%d%d%d", &a, &b, &c);
    cout << bfs();
    return 0;
}

FZU2150（双点BFS）

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
//连通集大于2个则输出-1
//连通集等于两个则各自bfs
//连通集等于1个则？爆搜！
//双起点bfs
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;

const int MAX_N = 20;
const int INF = 2e9 + 7;

int T, n, m;
char maze[MAX_N][MAX_N];
char book[MAX_N][MAX_N];
int ans;
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
int d[MAX_N][MAX_N];

typedef pair<int, int> pr;

queue<pr> que;

void my_fill(int x, int y)
{
    book[x][y] = '.';
    for(int i = 0; i < 4; ++i)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(0 <= nx && nx < n && 0 <= ny && ny < m
            && book[nx][ny] == '#')
            my_fill(nx, ny);
    }
}

bool check() //检查连通集是否大于两个
{
    int count = 0;
    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j < m; ++j)
        {
            if(book[i][j] == '#')
            {
                my_fill(i, j);
                count++;
            }
        }
    }
    if(count > 2) return false;
    return true;
}

int solve(int x, int y, int a, int b)
{
    int ret = 0;
    queue<pr> p;
    p.push(pr(x, y));
    p.push(pr(a, b));
    d[x][y] = d[a][b] = 0;

    while(p.size())
    {
        pr t = p.front();
        p.pop();
        for(int i = 0; i < 4; ++i)
        {
            int nx = t.first + dx[i];
            int ny = t.second + dy[i];
            if(0 <= nx && nx < n && 0 <= ny && ny < m && maze[nx][ny] == '#'
                && d[nx][ny] == -1)
            {
                ret = d[nx][ny] = d[t.first][t.second] + 1;
                p.push(pr(nx, ny));
            }
        }
    }

    for(int i = 0; i < n; ++i) //检查是否有点没有搜过（两个起点都在一个连通集的情况）
    {
        for(int j = 0; j < m; ++j)
        {
            if(maze[i][j] == '#' && d[i][j] == -1)
            {
                return INF;
            }
        }
    }
    return ret;
}

int main()
{
    scanf("%d", &T);
    for(int i = 0; i < T; ++i)
    {
        que = queue<pr>(); //初始化
        ans = INF;

        scanf("%d%d", &n, &m);
        for(int i = 0; i < n; ++i)
        {
            scanf("%s", maze[i]);
            for(int j = 0; j < m; ++j)
            {
                book[i][j] = maze[i][j];
                if(maze[i][j] == '#')
                {
                    que.push(pr(i, j));
                }
            }
        }

        if(!check())
        {
            printf("Case %d: -1\n", i + 1);
            continue;
        }

        if(que.size() <= 2)
        {
            printf("Case %d: 0\n", i + 1);
            continue;
        }

        while(que.size()) //总共que.size()个草的坐标，列举所有组合
        {
            pr t1 = que.front();
            que.pop();
            int count = que.size();
            while(count--)
            {
                pr t2 = que.front();
                que.pop();
                que.push(t2);
                memset(d, -1, sizeof(d));
                ans = min(ans, solve(t1.first, t1.second, t2.first, t2.second));
            }
        }
        printf("Case %d: %d\n", i + 1, ans);
    }
    return 0;
}

UVA11624（多点BFS）

F的初始位置有很多，用一个队列来存储F，j可达到的地方也用一个队列表示

然后就是双起点BFS了

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;

const int MAX_N = 1000 + 1;

typedef pair<int, int> pr;

int n;
int r, c;

char maze[MAX_N][MAX_N];
int d[MAX_N][MAX_N];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
int jx, jy;
int ret = 0;
queue<pr> F;

bool solve()
{
    queue<pr> qj;
    qj.push(pr(jx, jy));
    d[jx][jy] = 0;

    while(qj.size())
    {
        int count = F.size();
        while(count--)
        {
            pr t2 = F.front();
            F.pop();
            for(int i = 0; i < 4; ++i)
            {
                int nx = t2.first + dx[i];
                int ny = t2.second + dy[i];
                if(0 <= nx && nx < r && 0 <= ny && ny < c
                    && (maze[nx][ny] == '.' || maze[nx][ny] == 'J')) //火势可蔓延
                {
                    maze[nx][ny] = 'F';
                    F.push(pr(nx, ny));
                }
            }
        }

        count = qj.size();
        while(count--)
        {
            pr t = qj.front();
            qj.pop();
            for(int i = 0; i < 4; ++i)
            {
                int nx = t.first + dx[i];
                int ny = t.second + dy[i];
                if(0 <= nx && nx < r && 0 <= ny && ny < c)
                {
                    if(d[nx][ny] == -1 && maze[nx][ny] == '.')
                    {
                        d[nx][ny] = d[t.first][t.second] + 1;
                        qj.push(pr(nx, ny));
                    }
                }
                else
                {
                    ret = d[t.first][t.second] + 1;
                    return true;
                }
            }
        }
    }
    return false;
}

int main()
{
    // freopen("data.in","r",stdin);
    // freopen("data.out","w",stdout);
    scanf("%d", &n);
    for(int i = 0; i < n; ++i)
    {
        F = queue<pr>();
        memset(d, -1, sizeof(d));

        scanf("%d%d", &r, &c);
        for(int j = 0; j < r; ++j)
        {
            scanf("%s", maze[j]);
            for(int k = 0; k < c; ++k)
            {
                if(maze[j][k] == 'F')
                {
                    F.push(pr(j, k));
                }
                if(maze[j][k] == 'J')
                {
                    jx = j;
                    jy = k;
                }
            }
        }
        if(solve())
            printf("%d\n", ret);
        else
            printf("IMPOSSIBLE\n");
    }
    return 0;
}

POJ3984（DFS + 路径还原）

路径还原

我选择用一个栈同步DFS……

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
#include<cstdio>
#include<stack>
using namespace std;

const int MAX_N = 6;

int maze[MAX_N][MAX_N];
int d[MAX_N][MAX_N];

int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

int mini = 2e9;

typedef pair<int, int> pr;
stack<pr> s1, s2; 

void dfs(int x, int y)
{
    //printf("(%d, %d)\n", x, y);
    if(x == 4 && y == 4)
    {
        if((int)s1.size() < mini)
        {
            s2 = s1;
            mini = s1.size();
        }
        return ;
    }
    else
    {
        for(int i = 0; i < 4; ++i)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(0 <= nx && nx < 5 && 0 <= ny && ny < 5
                && !maze[nx][ny] && !d[nx][ny])
            {
                s1.push(pr(nx, ny));
                d[nx][ny] = 1;
                dfs(nx, ny);
                d[nx][ny] = 0;
                s1.pop();
            }
        }
    }
}

int main()
{
    for(int i = 0; i < 5; ++i)
        for(int j = 0; j < 5; ++j)
            scanf("%d", &maze[i][j]);
    s1.push(pr(0, 0));
    d[0][0] = 1;
    dfs(0, 0);

    stack<pr> s3;
    while(!s2.empty())
    {
        s3.push(s2.top());
        s2.pop();
    }
    while(!s3.empty())
    {
        printf("(%d, %d)\n", s3.top().first, s3.top().second);
        s3.pop();
    }
    return 0;
}

HDU1241（DFS求连通块）

简单的连通块搜索

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>

const int MAX_N = 100 + 1;

int n, m;
char map[MAX_N][MAX_N];

void dfs(int x, int y)
{
    for(int i = -1; i <= 1; ++i)
    {
        for(int j = -1; j <= 1; ++j)
        {
            int nx = x + i;
            int ny = y + j;
            if(0 <= nx && nx < n && 0 <= ny && ny < m
                && map[nx][ny] == '@')
            {
                map[nx][ny] = '*';
                dfs(nx, ny);
            }
        }
    }
}

int main()
{
    while(true)
    {
        int ans = 0;
        scanf("%d%d", &n, &m);
        if(!n) break;
        for(int i = 0; i < n; ++i)
        {
            scanf("%s", map[i]);
        }
        for(int i = 0; i < n; ++i)
        {
            for(int j = 0; j < m; ++j)
            {
                if(map[i][j] == '@')
                {
                    dfs(i, j);
                    ans++;
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

HDU1495（BFS + 枚举 + 思考）

枚举倒完水后各个容器内水的体积，然后BFS即可

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;

struct node
{
    int x;
    int y;
    int z;
};

int ans[102][102][102];

int solve(int S, int N, int M)
{
    if(S & 1) return -1;

    memset(ans, -1, sizeof(ans));
    ans[S][0][0] = 0;

    queue<node> que;
    node t;
    t.x = S, t.y = 0, t.z = 0;
    que.push(t);
    while(que.size())
    {
        t = que.front();
        que.pop();
        int count = 0;
        if(t.x == S / 2)
            count++;
        if(t.y == S / 2)
            count++;
        if(t.z == S / 2)
            count++;
        if(count == 2)
            return ans[t.x][t.y][t.z];

        node t1;
        if(t.x + t.y <= N) //A倒B
        {
            t1.x = 0;
            t1.y = t.x + t.y;
            t1.z = t.z;
        }
        else
        {
            t1.x = t.x + t.y - N;
            t1.y = N;
            t1.z = t.z;
        }
        if(ans[t1.x][t1.y][t1.z] == -1)
        {
            que.push(t1);
            ans[t1.x][t1.y][t1.z] = ans[t.x][t.y][t.z] + 1;
        }

        if(t.x + t.z <= M) //A倒C
        {
            t1.x = 0;
            t1.y = t.y;
            t1.z = t.x + t.z;
        }
        else
        {
            t1.x = t.x + t.z - M;
            t1.y = t.y;
            t1.z = M;
        }
        if(ans[t1.x][t1.y][t1.z] == -1)
        {
            que.push(t1);
            ans[t1.x][t1.y][t1.z] = ans[t.x][t.y][t.z] + 1;
        }

        if(t.y + t.z <= M) //B倒C
        {
            t1.x = t.x;
            t1.y = 0;
            t1.z = t.y + t.z;
        }
        else
        {
            t1.x = t.x;
            t1.y = t.y + t.z - M;
            t1.z = M;
        }
        if(ans[t1.x][t1.y][t1.z] == -1)
        {
            que.push(t1);
            ans[t1.x][t1.y][t1.z] = ans[t.x][t.y][t.z] + 1;
        }

        if(t.y + t.z <= N) //C倒B
        {
            t1.x = t.x;
            t1.y = t.y + t.z;
            t1.z = 0;
        }
        else
        {
            t1.x = t.x;
            t1.y = N;
            t1.z = t.y + t.z - N;
        }
        if(ans[t1.x][t1.y][t1.z] == -1)
        {
            que.push(t1);
            ans[t1.x][t1.y][t1.z] = ans[t.x][t.y][t.z] + 1;
        }

        t1.x = t.x + t.y; //B倒A
        t1.y = 0;
        t1.z = t.z;
        if(ans[t1.x][t1.y][t1.z] == -1)
        {
            que.push(t1);
            ans[t1.x][t1.y][t1.z] = ans[t.x][t.y][t.z] + 1;
        }

        t1.x = t.x + t.z; //C倒A
        t1.y = t.y;
        t1.z = 0;
        if(ans[t1.x][t1.y][t1.z] == -1)
        {
            que.push(t1);
            ans[t1.x][t1.y][t1.z] = ans[t.x][t.y][t.z] + 1;
        }
    }
    return -1;
}

int main()
{
    int S, N, M;
    while(true)
    {
        scanf("%d%d%d", &S, &N, &M);
        if(!S)
            break;
        int ret = solve(S, N, M);
        if(ret == -1)
            printf("NO\n");
        else
            printf("%d\n", ret);
    }
    return 0;
}

HDU2612（两点BFS）

可能有的@点无法到达，要排除

两个BFS，把结果相加即可

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
77
78
79
80
81
82
83
84
85
//简单bfs
//易错！！注意可能有@无法到达，要特判
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

const int MAX_N = 200 + 10;

int n, m;
char maze[MAX_N][MAX_N];
int ansY[MAX_N][MAX_N];
int ansM[MAX_N][MAX_N];
int YX, YY;
int MX, MY;
int ret = 1e9;

int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

typedef pair<int, int> pr;

void solve(int x, int y, int (& ans)[MAX_N][MAX_N])
{
    queue<pr> que;
    que.push(pr(x, y));
    while(que.size())
    {
        pr t = que.front();
        que.pop();
        for(int i = 0; i < 4; ++i)
        {
            int nx = t.first + dx[i];
            int ny = t.second + dy[i];
            if(0 <= nx && 0 <= ny && nx < n && ny < m && maze[nx][ny] != '#'
                && maze[nx][ny] != 'Y' &&maze[nx][ny] != 'M' && ans[nx][ny] == -1)
            {
                ans[nx][ny] = ans[t.first][t.second] + 1;
                que.push(pr(nx, ny));
            }
        }
    }
}

int main()
{
    while(scanf("%d%d", &n, &m) != EOF)
    {
        for(int i = 0; i < n; ++i)
        {
            scanf("%s", maze[i]);
            for(int j = 0; j < m; ++j)
            {
                if(maze[i][j] == 'Y')
                {
                    YX = i;
                    YY = j;
                }
                if(maze[i][j] == 'M')
                {
                    MX = i;
                    MY = j;
                }
            }
        }
        memset(ansY, -1, sizeof(ansY));
        ansY[YX][YY] = 0;
        solve(YX, YY, ansY);
        memset(ansM, -1, sizeof(ansM));
        ansM[MX][MY] = 0;
        solve(MX, MY, ansM);
        ret = 1e9;
        for(int i = 0; i < n; ++i)
        {
            for(int j = 0; j < m; ++j)
            {
                if(maze[i][j] == '@' && ansY[i][j] != -1 && ansM[i][j] != -1)
                    ret = min(ret, ansY[i][j] + ansM[i][j]);
            }
        }
        printf("%d\n", ret * 11);
    }
    return 0;
}

洛谷P1219（DFS，经典八皇后问题）

经典n皇后问题

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
#include<cstdio>

int n, sum;
int ans[14];
bool check[3][30];

void solve(int line)
{
    if(line > n)
    {
        sum++;
        if(sum > 3)
            return ;
        else
        {
            for(int i = 1; i <= n; i++)
            {
                printf("%d ", ans[i]);
            }
            printf("\n");
            return ;
        }
    }
    for(int i = 1; i <= n; i++)
    {
        if(!check[0][i] && !check[1][line+i] && !check[2][line+n-i])
        {
            ans[line] = i;
            check[0][i] = check[1][line+i] = check[2][line+n-i] = 1;
            solve(line+1);
            check[0][i] = check[1][line+i] = check[2][line+n-i] = 0;
        }
    }
}

int main()
{
    scanf("%d", &n);
    solve(1);
    printf("%d\n", sum);
    return 0;
}

洛谷P1019（DFS，暴力）

注意linkstr()函数返回的应该是最小重叠部分，而非最大

注意开头的字符串也要标记使用过一次

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
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;

const int MAX_N = 20 + 1;

int n;
int ans = 0;
char ch;
string str[MAX_N];
int used[MAX_N];

int linkstr(string str1, string str2)
{
    for(int i = 0; i < min((int)str1.length(), (int)str2.length()); ++i)
    {
        int flag = 1;
        for(int j = i; j >= 0; --j)
        {
            if(str2[i-j] != str1[str1.length() - j - 1])
                flag = 0;
        }
        if(flag)
            return i + 1;
    }
}

void dfs(string strnow, int lengthnow)
{
    ans = max(lengthnow, ans);
    for(int i = 0; i < n; ++i)
    {
        int len = linkstr(strnow, str[i]);
        if(used[i] && len)
        {
            used[i]--;
            dfs(str[i], str[i].length() + lengthnow - len);
            used[i]++;
        }
    }
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; ++i)
    {
        cin >> str[i];
        used[i] = 2;
    }
    cin >> ch;
    for(int i = 0; i < n; ++i)
    {
        if(str[i][0] == ch)
        {
            used[i]--;
            dfs(str[i], str[i].length());
            used[i]++;
        }
    }
    cout << ans << endl;
    return 0;
}
//最小重叠部分
//第一个开头的也要计算使用过

洛谷P1101（单向DFS）

使用字符串常量

参数包含方向

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
#include<cstdio>

const int MAX_N = 100 + 1;

char map[MAX_N][MAX_N];
char str[] = "yizhong";
char ans[MAX_N][MAX_N];
int n;

void dfs(int x, int y, int now, int dx, int dy)
{
    if(now == 6)
    {
        int nx = x;
        int ny = y;
        ans[nx][ny] = 'g';
        for(int i = 1; i <= 6; ++i)
        {
            nx -= dx;
            ny -= dy;
            ans[nx][ny] = str[6-i];
        }
    }
    else
    {
        int nx = x + dx;
        int ny = y + dy;
        if(nx >= 0 && nx < n && ny >= 0 && ny < n
            && map[nx][ny] == str[now + 1])
            dfs(nx, ny, now + 1, dx, dy);
    }
}

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; ++i)
    {
        scanf("%s", map[i]);
        for(int j = 0; j < n; ++j)
        {
            ans[i][j] = '*';
        }
    }
    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j < n; ++j)
        {
            if(map[i][j] == 'y')
            {
                for(int k = -1; k <= 1; ++k)
                {
                    for(int l = -1; l <= 1; ++l)
                    {
                        if(!k && !l)
                            continue;
                        dfs(i, j, 0, k, l);
                    }
                }
            }
        }
    }
    for(int i = 0; i < n; ++i)
    {
        puts(ans[i]);
    }
    return 0;
}

洛谷P1605（DFS求路径数）

简单题

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
#include<cstdio>

const int MAX_NM = 5 + 2;
const int INF = 1e9;

int map[MAX_NM][MAX_NM];
int d[MAX_NM][MAX_NM];
int n, m, t;
int sx, sy, gx, gy;
int ans = 0;
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

void dfs(int x, int y)
{
    if(x == gx && y == gy)
    {
        ans++;
        return ;
    }
    else
    {
        for(int i = 0; i < 4; ++i)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx > 0 && nx <= n && ny > 0 && ny <= m && map[nx][ny] != INF
                && !d[nx][ny])
            {
                d[nx][ny] = 1;
                dfs(nx, ny);
                d[nx][ny] = 0;
            }
        }
    }
}

int main()
{
    scanf("%d%d%d", &n, &m, &t);
    scanf("%d%d%d%d", &sx, &sy, &gx, &gy);
    for(int i = 0; i < t; ++i)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        map[x][y] = INF;
    }
    d[sx][sy] = 1;
    dfs(sx, sy);
    printf("%d\n", ans);
    return 0;
}
//起点坐标不要忘记标记使用过

洛谷P1162（BFS求闭合圈）

先把边界预先染成其它颜色

染色时，先染色再push()，避免重复计算

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
77
78
79
80
81
#include<cstdio>
#include<queue>
using namespace std;

const int MAX_N = 30 + 1;

typedef pair<int, int> pr;

int n;
int map[MAX_N][MAX_N];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

void bfs(int x, int y, int c)
{
    queue<pr> que;
    que.push(pr(x, y));
    while(que.size())
    {
        pr p = que.front();
        que.pop();
        map[p.first][p.second] = c;
        for(int i = 0; i < 4; ++i)
        {
            int nx = p.first + dx[i];
            int ny = p.second + dy[i];
            if(0 <= nx && nx < n && 0 <= ny && ny < n
                && map[nx][ny] == 0)
            {
                map[nx][ny] = c;
                que.push(pr(nx, ny));
            }
        }
    }
}

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j < n; ++j)
        {
            scanf("%d", &map[i][j]);
        }
    }
    for(int i = 0; i < n; ++i)
    {
        if(!map[i][0])
            bfs(i, 0, 3);
        if(!map[i][n-1])
            bfs(i, n-1, 3);
        if(!map[0][i])
            bfs(0, i, 3);
        if(!map[n-1][i])
            bfs(n-1, i, 3);
    }
    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j < n; ++j)
        {
            if(map[i][j] == 0)
            {
                bfs(i, j, 2);
            }
        }
    }
    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j < n; ++j)
        {
            if(map[i][j] == 3)
                printf("0 ");
            else
                printf("%d ", map[i][j]);
        }
        printf("\n");
    }
    return 0;
}
//先染色再放进去，不然会超时甚至爆栈

洛谷P1141（BFS，染色）

读错题了orz，不是求从(x, y)所能达到的最远距离，而是从(x, y)所能达到的最多格子数

那么求连通集就好，一个连通集内，所能达到的地方相同

比如在学校是一个连通集，不管是从教学楼出发，还是从寝室出发，最终能到达的地方都是整个学校

  • %1d这样的输入格式
  • 小技巧，给d赋不同的值，然后映射ret
  • ret数组不要开小了……
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
#include<cstdio>
#include<queue>
using namespace std;

const int MAX_N = 1e3 + 1;

int maze[MAX_N][MAX_N];
int d[MAX_N][MAX_N];
int ret[MAX_N * MAX_N + 1];

int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

int ans = 1;
int n, m;
int num = 1;

typedef pair<int, int> pr;

queue<pr> que;

void bfs(int x, int y, int num)
{
    d[x][y] = num;
    que.push(pr(x, y));
    while(!que.empty())
    {
        pr t = que.front();
        que.pop();
        int nx, ny;
        for(int i = 0; i < 4; ++i)
        {
            nx = t.first + dx[i];
            ny = t.second + dy[i];
            if(0 <= nx && nx < n && 0 <= ny && ny < n && !d[nx][ny]
                && maze[nx][ny] != maze[t.first][t.second])
            {
                d[nx][ny] = num;
                ans++;
                que.push(pr(nx, ny));
            }
        }
    }
    ret[num] = ans;
    ans = 1;
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            scanf("%1d", &maze[i][j]); //输入格式

    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j < n; ++j)
        {
            if(!d[i][j])
                bfs(i, j, num++);
        }
    }

    for(int i = 0; i < m; ++i)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", ret[d[a-1][b-1]]);
    }
    return 0;
}

洛谷P1443（非上下左右移动的BFS）

改变方向数据即可

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
#include<cstdio>
#include<queue>
#include<utility>
using namespace std;

const int MAX_MN = 400 + 1;

typedef pair<int, int> pr;

int map[MAX_MN][MAX_MN];
int m, n, sx, sy;
int dx[] = {2, 2, 1, 1, -1, -1, -2, -2};
int dy[] = {1, -1, 2, -2, 2, -2, 1, -1};

void bfs()
{
    queue<pr> que;
    que.push(pr(sx-1, sy-1));
    while(que.size())
    {
        pr p = que.front();
        que.pop();
        for(int i = 0; i < 8; ++i)
        {
            int nx = p.first + dx[i];
            int ny = p.second + dy[i];
            if(0 <= nx && nx < m && 0 <= ny && ny < n
                && map[nx][ny] == -1)
            {
                map[nx][ny] = map[p.first][p.second] + 1;
                que.push(pr(nx, ny));
            }
        }
    }
}

int main()
{
    scanf("%d%d%d%d", &m, &n, &sx, &sy);
    for(int i = 0; i < m; ++i)
    {
        for(int j = 0; j < n; ++j)
        {
            map[i][j] = -1;
        }
    }
    map[sx-1][sy-1] = 0;
    bfs();
    for(int i = 0; i < m; ++i)
    {
        for(int j = 0; j < n; ++j)
        {
            printf("%-5d", map[i][j]);
        }
        printf("\n");
    }
    return 0;
}
//注意格式

总结

何为搜索？

我接触的第一道搜索题是白书上的部分和问题。是一道简单的BFS，当时由于对递归的理解不够，导致花了好多天才理解为什么要这么写。到我能真正写出DFS那是更后面的事了。

后来我会熟练地写地图上的搜索了，并天真地以为搜索就是指图的搜索。在一个图中给出入口出口，寻找最短路径或者求连通块便是搜索。我做了很多板子题，并自得其乐。洛谷P1101，洛谷P1605，洛谷P1162，洛谷P1141。

再后来逐渐接触一些稍微变形点的题，比如三维的啦POJ2251，像马那样跳跃的啦洛谷P1443，多点一起的搜索啦FZU2150，UVA11624，八皇后相关的啦洛谷P1219，POJ1321，路径还原啦POJ3984，POJ3414

再后来，我就自闭了……因为发现这个时候剩下的题都是没什么思路的，它不是一个地图，我想象不出它的样子，无法把它们套进搜索的模型里。

好在随着时间的流逝，我也逐渐开窍了。懂得了地图只是搜索的一个很直观的表现。搜索是一个状态根据一个规则到达另一份状态，后者再根据同一个规则到达下一份状态，直至搜完所有的可能或者得到目标值，应该也是一种暴力的方法（莽夫的智慧）。而BFS还是DFS只是搜索策略的不同罢了。