洛谷官方题单——搜索题解

搜索一般我们都分为DFS和BFS，其中设计到回溯，剪枝的技巧。

但是一般我们都将搜索视作暴力，但是比纯粹的暴力会快不少，并且可以通过搜索获得小规模问题从而帮助推导后续的问题。

最后提醒一下，DFS是存在最大值性质的，BFS是存在最小值性质的，因此除非题目挖坑，否则不要轻易的用BFS解决最小值问题。

题目0：八皇后 Checker Challenge

八皇后问题是学习数据结构的时候的必学问题了，实际上考察的是DFS+剪枝，因为有些方法在搜索过程中，已经违反了题目的要求，没有必要继续搜索下去了。注意回溯的时候记得恢复状态

#pragma warning(disable:4996)
#include<stdio.h>
int ans[20], book[3][30], sum, n;
void dfs(int x){
    if (x > n){
        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 ((!book[0][i]) && (!book[1][x + i]) && (!book[2][x + n - i])) {
            //同一行，同一列，同一对角线,其中同一对角线可以考虑结合直线的一次方程
            ans[x] = i;
            book[0][i] = 1; book[1][x + i] = 1; book[2][x + n - i] = 1;
            dfs(x + 1);
            book[0][i] = 0; book[1][x + i] = 0; book[2][x + n - i] = 0;
        }
    }
}
int main(){
    scanf("%d", &n);
    dfs(1);
    return 0 * printf("%d\n", sum);
}

题目1：kkksc03考前临时抱佛脚

原题，略。

题目2：马的遍历

BFS模板题，只需要存储马可以跑到的地方然后逐个填数字即可，注意最后需要把起点归0。

#include<queue>
#include<string.h>
#include<stdio.h>
using namespace std;
typedef long long ll;
int xx[8] = { 2, -2, 2, -2, -1, 1, -1, 1 };
int yy[8] = { 1, 1, -1, -1, 2, 2, -2, -2 };
int n, m, a, b, map[402][402];
struct Node {
    int x, y, s;
};
int main() {
    scanf("%d%d%d%d", &n, &m, &a, &b);
    queue<Node>q;
    map[a][b] = 0;
    memset(map, -1, sizeof(int) * 161604);
    Node t;
    t.x = a, t.y = b, t.s = 0;
    q.push(t);
    while (!q.empty()) {
        for (int i = 0; i < 8; i++) {
            int dx = q.front().x + xx[i];
            int dy = q.front().y + yy[i];
            if (dx >= 1 && dx <= n && dy >= 1 && dy <= m && map[dx][dy] == -1) {
                Node temp;
                temp.x = dx, temp.y = dy, temp.s = q.front().s + 1;
                q.push(temp);
                map[dx][dy] = q.front().s + 1;
            }
        }
        q.pop();
    }
    map[a][b] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++)
            printf("%-5d", map[i][j]);
        printf("\n");
    }
    return 0;
}

题目3：奇怪的电梯

要找最小值，首先想到使用宽搜的方法，即我们将开始的地方放入队列，然后我们得到队头元素，然后按照题目要求到达能到（上和下）的地方，并且将这个地方入队。一直循环到队列空，那么到时候ans存储的就是所需要的按钮次数。

#include<queue>
#include<stdio.h>
using namespace std;
int n, a, b, F[205];
bool vis[205];
struct Floor { 
    int id, step; 
}ans;
int main(){
    scanf("%d%d%d", &n, &a, &b);
    queue<Floor> q;
    for (int i = 1; i <= n; i++) scanf("%d", &F[i]);
    Floor temp{ a,0 };
    q.push(temp);
    while (q.size()){
        ans = q.front(); 
        q.pop();
        if (ans.id == b) break;
        if (ans.id + F[ans.id] <= n && !vis[ans.id + F[ans.id]]){
            Floor temp_1{ ans.id + F[ans.id], ans.step + 1 };
            q.push(temp_1);
            vis[ans.id + F[ans.id]] = 1;
        }
        if (ans.id - F[ans.id] >= 1 && !vis[ans.id - F[ans.id]]){
            Floor temp_2{ ans.id - F[ans.id], ans.step + 1 };
            q.push(temp_2);
            vis[ans.id - F[ans.id]] = 1;
        }
    }
    if (ans.id == b) return 0 * printf("%d\n", ans.step);
    else return 0 * printf("-1");
}

题目4：Meteor Shower S

最少时间，依旧需要宽搜，但是这道题是属于很多细节的题，所以看代码的注释把。

#include<queue>
#include<stdio.h>
#include<string.h>
using namespace std;
struct Meteor{
    int x, y, time;
}; 
int t[305][305], book[305][305]; 
int dx[4] = { 0,0,1,-1 }, dy[4] = { 1,-1,0,0 };
queue<Meteor>q;
int main(){
    int m;
    scanf("%d", &m);
    memset(t, -1, sizeof(t));
    for (int i = 1; i <= m; i++){
        int temp_x, temp_y, temp_t;
        scanf("%d%d%d", &temp_x, &temp_y, &temp_t);
        if (temp_t < t[temp_x][temp_y] || t[temp_x][temp_y] == -1)
            t[temp_x][temp_y] = temp_t;
        for (int i = 0; i < 4; i++){
            int nx = temp_x + dx[i], ny = temp_y + dy[i];
            if (nx >= 0 && ny >= 0 && (t[nx][ny] == -1 || temp_t < t[nx][ny]))
                t[nx][ny] = temp_t; 
        }
    }
    Meteor begin{ 0,0,0 };
    book[0][0] = 1;
    q.push(begin);
    while (!q.empty()){
        Meteor p = q.front();
        q.pop();
        for (int i = 0; i < 4; i++){
            int now_x = p.x + dx[i], now_y = p.y + dy[i];
            if (now_x >= 0 && now_y >= 0 && book[now_x][now_y] == 0 && (t[now_x][now_y] == -1 || p.time + 1 < t[now_x][now_y])){
                Meteor ans{ now_x ,now_y ,p.time + 1 };
                book[now_x][now_y] = 1;
                q.push(ans);
                if (t[now_x][now_y] == -1) return 0 * printf("%d\n", ans.time);
            }
        }
    }
    return 0 * printf("-1\n");
}

题目5：选数

原题，略。

题目6：PERKET

原题，略。

题目7：吃奶酪

原题，略。

题目8：迷宫

要找到所有的通路，那么就要搜索所有的可能，找某条道路的方法是DFS，所以我们DFS后，ans++即可。

#include<stdio.h>
#include<string.h>
using namespace std;
int map[6][6];
bool temp[6][6];
int dx[4] = { 0,0,1,-1 };
int dy[4] = { -1,1,0,0 };
int ans, end_x, end_y, begin_x, begin_y;
void dfs(int x, int y){
    if (x == end_x && y == end_y){
        ans++;
        return;
    }
    else{
        for (int i = 0; i <= 3; i++){
            if (temp[x + dx[i]][y + dy[i]] == 0 && map[x + dx[i]][y + dy[i]] == 1){
                temp[x][y] = 1;
                dfs(x + dx[i], y + dy[i]);
                temp[x][y] = 0;
            }
        }
    }
}
int main(){
    int N, T, M, ob_x, ob_y;
    scanf("%d%d%d%d%d%d%d", &N, &M, &T, &begin_x, &begin_y, &end_x, &end_y);
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++) map[i][j] = 1;
    for (int i = 1; i <= T; i++){
        scanf("%d%d", &ob_x, &ob_y);
        map[ob_x][ob_y] = 0;
    }
    dfs(begin_x, begin_y);
    return 0 * printf("%d\n", ans);
}

题目9：单词接龙

找到最长的字符串，那么我们就联想到DFS。维护一个全局变量ans，然后每次进入一层DFS都直接和之前的ans和的temp_ans取最大值，最后结束即可。

难点在于重叠的处理，check函数即可。

#include <iostream>
#include <string>
using namespace std;
int ans = 0, n, dic_cnt[30];
string dic[30], start;
int max(int x, int y) { return x > y ? x : y; }
bool check(string origin, string checked, int check_start) {
    int len = origin.length();
    for (int i = 0; i < check_start; i++) 
        if ((len - check_start + i < 0) || (origin[len - check_start + i] != checked[i])) 
            return false;
    return true;
}
void add(string& origin, string added, int add_start) {
    int len = added.length();
    for (int i = add_start; i < len; i++) origin += added[i];
}
void dfs(string now){
    int x = now.length();
    ans = max(ans, x);
    for (int i = 1; i <= n; i++) {
        if (dic_cnt[i] >= 2) continue;
        int len = dic[i].length();
        for (int j = 1; j <= len; j++) {
            if (check(now, dic[i], j)) {
                string temp = now;
                add(temp, dic[i], j);
                if (temp == now) continue;
                dic_cnt[i]++;
                dfs(temp);
                dic_cnt[i]--;
            }
        }
    }
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> dic[i];
    cin >> start;
    dfs(start);
    cout << ans << endl;
    return 0;
}

题目10：单词方阵

DFS+八方向检查，DFS接口额外增加一个项确定方向，代码有坑请谨慎复制。

#include<iostream>
struct Cordinate{
    int x, y;
}memo[10];
char map[105][105], key[] = "yizhong";
int book[105][105];
int d[8][2] = { {-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1} };
void dfs(int x, int y, int direct, int cur){
    if (cur == 7) {
        for (int i = 0; i < 7; i++)
            book[memo[i].x][memo[i].y] = 1;
    }
    else {
        int dx = x + d[direct][0], dy = y + d[direct][1];
        if (cur == 6 || map[dx][dy] == key[cur + 1]) {
            memo[cur].x = x, memo[cur].y = y;
            dfs(dx, dy, direct, cur + 1);
        }
    }
}
int main(){
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%s", map[i]);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (map[i][j] == 'y') {
                for (int k = 0; k < 8; k++) {
                    int x = i + d[k][0], y = j + d[k][1];
                    if (map[x][y] == 'i') dfs(i, j, k, 0);
                }
            }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            if (book[i][j]) printf("%c", map[i][j]);
            else printf("*");
        printf("\n");
    }
    return 0;
}

题目11：自然数拆分

典型的深搜题目，粗暴的不能再粗暴了。

#include<stdio.h>
int n, ans[11] = { 1 }, m;
void print(int num) {
    for (int i = 1; i < num; i++) printf("%d+", ans[i]);
    printf("%d\n", ans[num]);
}
void dfs(int len) {
    for (int i = ans[len - 1]; i <= m; i++) {
        if (i == n) continue;
        ans[len] = i, m -= i;
        if (m == 0) print(len);
        else dfs(len + 1);
        m += i;
    }
}
int main() {
    scanf("%d", &n);
    m = n;
    dfs(1);
    return 0;
}

题目12：Lake Counting S

连通块的典型题目，BFS和DFS均可，就看自己怎么玩。

下面是BFS，但是TLE了别怪我嗷。

#pragma warning(disable:4996)
#include<stdio.h>
#include<queue>
using namespace std;
struct cordinate {
    int x, y;
};
queue<cordinate> q;
int dx[8] = { 1,0,-1,0,1,1,-1,-1 };
int dy[8] = { 0,1,0,-1,1,-1,-1,1 };
int n, m, ans;
char map[105][105];
int main() {
    scanf("%d%d", &n, &m);
    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] == 'W') {
                cordinate temp{ i,j };
                q.push(temp);
                while (!q.empty()) {
                    map[q.front().x][q.front().y] = '.';
                    for (int k = 0; k < 8; k++) {
                        int now_x = q.front().x + dx[k], now_y = q.front().y + dy[k];
                        if (now_x >= 0 && now_x < n && now_y >= 0 && now_y < m && map[now_x][now_y] == 'W') {
                            cordinate temp{ now_x,now_y };
                            q.push(temp);
                        }
                    }
                    q.pop();
                }
                ans++;
            }
        }
    }
    return 0 * printf("%d\n", ans);
}

DFS

#include<iostream>
#include<stdio.h>
using namespace std;
int dx[8] = { -1,-1,-1,0,0,1,1,1 };
int dy[8] = { -1,0,1,-1,1,-1,0,1 };
int n, m, ans;
char map[105][105];
void dfs(int x, int y){
    int now_x, now_y;
    map[x][y] = '.';
    for (int i = 0; i < 8; i++){
        int now_x = x + dx[i], now_y = y + dy[i];
        if (now_x<1 || now_x>n || now_y<1 || now_y>m || map[now_x][now_y] == '.') continue;
        map[now_x][now_y] = '.';
        dfs(now_x, now_y);
    }
}
int main(){
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> map[i][j];//为了不想处理空格不择手段
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            if (map[i][j] == 'W'){
                ans++;
                dfs(i, j);
            }
        }
    }
    return 0 * printf("%d\n", ans);
}

题目13：填涂颜色

DFS+染色，也是搜索的基本用途了。

#include<stdio.h>
int book[32][32], map[32][32];
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
int n;
void dfs(int x, int y) {
    if (x<0 || x>n + 1 || y<0 || y>n + 1 || book[x][y] != 0) return;
    book[x][y] = 1;
    for (int i = 0; i < 4; i++) dfs(x + dx[i], y + dy[i]);
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            scanf("%d", &map[i][j]);
            if (map[i][j] == 0) book[i][j] = 0;
            else book[i][j] = 2;
        }
    dfs(0, 0);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            if (book[i][j] == 0) printf("2 ");
            else printf("%d ", map[i][j]);
        printf("\n");
    }
    return 0;
}

题目14：字串变换

讲真他不放在这个踢单我真会认为是一个字符串写自动机的问题- -。

首先是最小步骤，因此我们应该优先想到BFS。同时由于STL=sometimes time limit，所以这个地方为了防止TLE应当手写队列。

其核心就是字符串入队看一下有无可修改方法，把修改之后的字符串入队列，记录修改的次数。

当然如果你不想用string的库函数，那么您可以手写KMP。

#pragma warning(disable:4996)
#include<iostream>
#include<string>
#include<stdio.h>
using namespace std;
string a, b, from[7], to[7];
struct Queue {
    string cur;
    int cnt;
}q[2000000];
int main(){
    cin >> a >> b;
    int cnt = 1, q_head = 0, q_tail = 1;
    while (cin >> from[cnt] >> to[cnt])cnt++;
    cnt--, q[q_tail].cur = a, q[q_tail].cnt = 0;
    while (q_head < q_tail){
        q_head++;
        if (q[q_head].cnt > 10) return 0 * printf("NO ANSWER!\n");
        for (int j = 1; j <= cnt; j++){
            int change_pos = q[q_head].cur.find(from[j], 0);
            while (1){
                if (change_pos == -1) break;
                else{
                    q_tail++;
                    q[q_tail].cur = q[q_head].cur, q[q_tail].cnt = q[q_head].cnt + 1;
                    q[q_tail].cur.replace(change_pos, from[j].size(), to[j]);
                    if (q[q_tail].cur == b) return 0 * printf("%d\n", q[q_tail].cnt);
                    change_pos = q[q_head].cur.find(from[j], change_pos + 1);
                }
            }
        }
    }
    return 0;
}

题目15：Corn Maze S

很简单细节很多的BFS（因为要找最短时间），简单来说就是：判断装置自己判断自己，导致死循环，地图的处理以及其他乱七八糟的小坑点。

#include<stdio.h>
#include<iostream>
using namespace std;
int map[500][500], book[500][500], n, m, end_x, end_y, trans_pair_x, trans_pair_y;
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
struct node{
    int x, y, time;
} ans[100050];
void find_trans(int x, int y){
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            if (!(i == x && j == y)){
                if (map[i][j] == map[x][y]){
                    trans_pair_x = i, trans_pair_y = j;
                    return;
                }
            }
        }
    }
}
int bfs(){
    int head = 0, tail = 1;
    do{
        head++;
        if (map[ans[head].x][ans[head].y] >= 'A' && map[ans[head].x][ans[head].y] <= 'Z'){
            find_trans(ans[head].x, ans[head].y);
            ans[head].x = trans_pair_x;
            ans[head].y = trans_pair_y;
        }
        for (int i = 0; i < 4; i++){
            int now_x = ans[head].x + dx[i], now_y = ans[head].y + dy[i];
            if (map[now_x][now_y] != 0 && book[now_x][now_y] == 0){
                book[now_x][now_y] = 1;
                tail++;
                ans[tail].x = now_x, ans[tail].y = now_y, ans[tail].time = ans[head].time + 1;
                if (now_x == end_x && now_y == end_y)return 0 * printf("%d\n", ans[tail].time);
            }
        }
    } while (head < tail);
}
int main(){
    char s;
    int begin_x, begin_y;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            cin >> s;
            if (s == '.') map[i][j] = 1;
            if (s >= 'A' && s <= 'Z') map[i][j] = s;
            if (s == '@'){
                begin_x = i, begin_y = j;
                map[i][j] = 1;
            }
            if (s == '='){
                end_x = i, end_y = j;
                map[i][j] = 1;
            }
        }
    }
    book[begin_x][begin_y] = 1, ans[1].x = begin_x, ans[1].y = begin_y;
    bfs();
    return 0;
}

三位数以1开头的只剩下四个数据结构的内容了，说明入门提单快刷完了（洛谷官方题单用的国外命名方式，因此1开头是基础，2开头是进阶。水题就快刷没了（贼难受）。

下一次更新就是数据结构的线性表了，实际上这部分的题就是基本的四个线性表：数组，链表，栈，队列的应用，里面或多或少牵扯到指针和其他的细节，反正不难便是了。