2024.1.27 搜索习题
|
18,655
|
0
|
搜索,集训

3121 字
|
30 分钟

A – 马的遍历

题目：

Description

有一个 n×m 的棋盘，在某个点(x,y)上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。

Input

输入只有一行四个整数，分别为 n,m,x,y。

Output

一个 n×m 的矩阵，代表马到达某个点最少要走几步（不能到达则输出 −1）。

对于全部的测试点，保证 1≤x≤n≤400，1≤y≤m≤400。

nenu寒假搜索练习 – Virtual Judge (vjudge.net)

思路：

这道题其实看到题目的第一反应就是dfs，因为dfs去解决这个问题很容易，代码也很好实现，但是搜索中会有很多重复的路径，把马可能走的所有情况都遍历了，时间是相当久的，所以就会TLE（time limited exceed）。

既然dfs走不通，我们就用bfs来搜索。

我们来梳理一下bfs广度优先搜索的思路。

先把我们要搜索的第一个节点加入队列，然后弹出队列的第一个节点，看看其有那些子节点，把所有的子节点加入队列。

然后我们再弹出此时队列里的第一个节点，然后继续扩展其子节点。直到最后队列为空结束。

所以这道题的思路就是，我们先加入马最开始所在的（x，y）节点，然后扩展它下一步能到的所有位置加入队列，然后再弹出队列的第一个节点，继续扩展。这样当我们bfs一遍之后，就已经更新过所有点的步数了。

代码DFS版本（TLE）：

#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int n,m,x,y;
int mx[1005][1005];
int dx[8]={2,-2,2,-2,-1,1,-1,1};
int dy[8]={1,1,-1,-1,2,2,-2,-2};
void dfs(int x,int y,int dis){
    if(x <= 0 || y <= 0 || x > n || y > m){
        return ;
    }

    mx[x][y] = dis;
    int nx,ny;
    for(int i = 0;i < 8;i++){
        nx = x + dx[i];
        ny = y + dy[i];
        if(dis + 1 < mx[nx][ny] || mx[nx][ny] == INF){
            dfs(nx,ny,dis + 1);
        }
    }
}
int main() {
    
    cin >> n >> m >> x >> y;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            mx[i][j] = INF;
        }
    }
    dfs(x,y,0);
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            if(mx[i][j] != INF)
                cout << mx[i][j] << " ";
            else cout << -1 << " ";
        }
        cout << "\n";
    }
}

代码BFS版本（AC）：

#include <bits/stdc++.h>
using namespace std;

// 定义一个结构体来保存坐标和步数
struct Node {
    int x, y, dist;
};

int n, m, x, y;
int mx[1005][1005];
int dx[8] = {-2, -2, -1, -1, 2, 2, 1, 1};
int dy[8] = {1, -1, 2, -2, 1, -1, 2, -2};

void bfs(int x, int y) {
    queue<Node> q;
    q.push({x, y, 0});
    mx[x][y] = 0;

    while (!q.empty()) {
        Node node = q.front();
        q.pop();
        for (int i = 0;i < 8;i++) {
            int nx = node.x + dx[i];
            int ny = node.y + dy[i];
            //如果这个点合理存在且没被访问过
            if (nx > 0 && ny > 0 && nx <= n && ny <= m && mx[nx][ny] == -1) {
                mx[nx][ny] = node.dist + 1;
                q.push({nx, ny, mx[nx][ny]});
            }
        }
    }
}

int main() {
    cin >> n >> m >> x >> y;
    memset(mx,-1,sizeof(mx));

    bfs(x, y);

    for (int i = 1; i <= n;i++) {
        for (int j = 1; j <= m;j++) {
            cout << left << setw(5) << mx[i][j];
        }
        cout << "\n";
    }
}

B – 高手去散步

题目：

Background

高手最近谈恋爱了。不过是单相思。“即使是单相思，也是完整的爱情”，高手从未放弃对它的追求。今天，这个阳光明媚的早晨，太阳从西边缓缓升起。于是它找到高手，希望在晨读开始之前和高手一起在鳌头山上一起散步。高手当然不会放弃这次梦寐以求的机会，他已经准备好了一切。

Description

鳌头山上有 n 个观景点，观景点两两之间有游步道共 m 条。高手的那个它，不喜欢太刺激的过程，因此那些没有路的观景点高手是不会选择去的。另外，她也不喜欢去同一个观景点一次以上。而高手想让他们在一起的路程最长（观景时它不会理高手），已知高手的穿梭机可以让他们在任意一个观景点出发，也在任意一个观景点结束。

Input

第一行，两个用空格隔开的整数 n、m。之后 m 行，为每条游步道的信息：两端观景点编号、长度。

Output

一个整数，表示他们最长相伴的路程。

对于 100%100% 的数据：n≤20，m≤50，保证观景点两两之间不会有多条游步道连接。

nenu寒假搜索练习 – Virtual Judge (vjudge.net)

思路：

简单总结一下，就是一个无向加权图，要找到其中最长的一条路径，数据量很小，可以用邻接矩阵来处理。

首先我们用邻接矩阵存图之后，来思考一下怎么找到最长的一条路径。比如我们任选一个起点，在图上搜索，计算所有可能的路径，我们搜索一下，就能得到从该点出发的最长长度。我们遍历，把每个点作为起点出发的情况都考虑一遍就行。

因为数据量很小，所以我们用dfs来搜索就行，毕竟dfs的实现非常容易。

代码DFS版本（AC）：

#include <bits/stdc++.h>
using namespace std;

int mx[100][100];
int vis[100];
int n,m;
int ans = 0;

void dfs(int x,int dis){
    ans = max(ans,dis);
    for(int i = 1;i <= n;i++){
        //没有路
        if(!mx[x][i]){
            continue;
        }else{
            //有路,先判断有没有被访问过。被访问过的话就换一条
            if(!vis[i]){
                vis[i] = 1;
                dfs(i,dis + mx[x][i]);
                vis[i] = 0;
            }else{
                continue;
            }
        }
    }
}

int main() {

    cin >> n >> m;
    for(int i = 1;i <= m;i++){
        int a,b,w;
        cin >> a >> b >> w;
        mx[a][b] = w;
        mx[b][a] = w;
    }
    for(int i = 1;i <= n;i++){
        vis[i] = 1;
        dfs(i,0);
        vis[i] = 0;
    }
    cout << ans << "\n";
}

C – 小埋与扫雷

题目：

Background

小埋总是在家中打游戏，一天，她突然想玩Windows自带的扫雷，在一旁的哥哥看见了，想起了自己小时候信息课在机房玩扫雷的日子，便兴致勃勃地开始教小埋扫雷。然而，小埋还是不明白 3bv（Bechtel’s Board Benchmark Value，每局将所有非雷的方块点开所需最少左键点击数，参见扫雷网的教程 ）怎么算，于是她找到了你。

img

Description

小埋会告诉你一盘扫雷，用一个 n×m 的矩阵表示，1 是雷 ，0 不是雷，请你告诉她这盘扫雷的 3bv 。

周围八格没有“雷”且自身不是“雷”的方格称为“空格”，周围八格有“雷”且自身不是“雷”的方格称为“数字”，由“空格”组成的八连通块称为一个“空”。3bv = 周围八格没有“空格”的“数字”个数 + “空”的个数。

如果看不懂上面的计算方式，可以看题目背景中给出的教程，或者看下面的样例解释。

注：八连通

Input

第一行有两个整数 n 和 m，代表这盘扫雷是一个 n×m 的矩阵。

后面的 n 行每行有 m 个整数，表示这个矩阵，每个数字为 0 或 1，1 代表是雷，0 代表不是雷。

Output

一个整数，代表这盘扫雷的 3bv 。

1≤n,m≤1000

nenu寒假搜索练习 – Virtual Judge (vjudge.net)

思路：

这题除了题意比较难懂以外，其实挺好写的，就是代码量有点长（笔者还读假题了）。

其实做好判断就可以了。判断谁是空格，谁是雷，谁是数字。然后根据题意做dfs搜索就行。

笔者的思路是先去找空格，然后得到空格的矩阵。dfs搜索这个矩阵，找出空的个数。

然后再去找四周有雷没空格的数字，遍历一遍矩阵的每个位置。每个位置都上下左右八个方向做个判断就行，如果满足就＋1。

代码DFS版本（AC）：

#include<bits/stdc++.h>
using namespace std;
int mx[1005][1005];
int vis[1005][1005];
int n,m;
int dx[] = {1,-1,0};
int dy[] = {1,-1,0};
int check(int x,int y){
	int flag = 0;
	//九个格子都为0，才是空格
	for(int i = 0;i < 3;i++){
		for(int j = 0;j < 3;j++){
			int nx = x + dx[i];
			int ny = y + dy[j];
			if(nx <= 0 || ny <= 0 || nx > n || ny > m){
				continue;
			}
			if(mx[nx][ny] != 0) flag = 1;
		}
	}
	if(flag) return 0;
	else return 1;
}
int dfs(int x,int y){
	if(x <= 0 || y <= 0 || x > n || y > m || vis[x][y] == 0){
		return 0;
	}
	vis[x][y] = 0;
	return 1 + dfs(x - 1,y) + dfs(x + 1,y) + dfs(x,y + 1) + dfs(x,y - 1) + 
	dfs(x + 1,y + 1) + dfs(x - 1,y + 1) + dfs(x + 1,y - 1) + dfs(x - 1,y - 1) ;
}
int main(){

	cin >> n >> m;
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= m;j++){
			cin >> mx[i][j];
		}
	}
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= m;j++){
			vis[i][j] = check(i,j);
		}
	}
	int cnt = 0;
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= m;j++){
			if(dfs(i,j) > 0){
				cnt++;
			}
		}
	}

	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= m;j++){
			if(mx[i][j]) continue;
			int flag = 0;
			//(i,j)上下左右都不是空格，且存在雷
			for(int k = 0;k < 3;k++){
				for(int l = 0;l < 3;l++){
					int nx = i + dx[k];
					int ny = j + dy[l];
					if(nx <= 0 || ny <= 0 || nx > n || ny > m ){
						continue;
					}
					if(check(nx,ny)) flag = 1;//说明有空格
				}
			}
			//有空格不行
			if(flag){
				flag = 0;
				continue;
			}
			flag = 0;
			//没空格的时候就找雷
			for(int k = 0;k < 3;k++){
				for(int l = 0;l < 3;l++){
					int nx = i + dx[k];
					int ny = j + dy[l];
					if(nx <= 0 || ny <= 0 || nx > n || ny > m ){
						continue;
					}
					if(mx[nx][ny] == 1) flag = 1;//说明有空格
				}
			}
			if(flag){
				flag = 0;
				cnt++;
			}
		}
	}
	cout << cnt << "\n";
}

彩蛋(求成最大空的大小了）：

#include<bits/stdc++.h>
using namespace std;
int mx[1005][1005];
int vis[1005][1005];
int n,m;
int dx[] = {1,-1,0};
int dy[] = {1,-1,0};
int check(int x,int y){
	int flag = 0;
	//九个格子都为0，才正确
	for(int i = 0;i < 3;i++){
		for(int j = 0;j < 3;j++){
			int nx = x + dx[i];
			int ny = y + dy[j];
			if(nx <= 0 || ny <= 0 || nx > n || ny > m){
				continue;
			}
			if(mx[nx][ny] != 0) flag = 1;
		}
	}
	if(flag) return 0;
	else return 1;
}
int dfs(int x,int y){
	if(x <= 0 || y <= 0 || x > n || y > m || vis[x][y] == 0){
		return 0;
	}
	vis[x][y] = 0;
	return 1 + dfs(x - 1,y) + dfs(x + 1,y) + dfs(x,y + 1) + dfs(x,y - 1);
}
int main(){

	cin >> n >> m;
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= m;j++){
			cin >> mx[i][j];
		}
	}
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= m;j++){
			vis[i][j] = check(i,j);
		}
	}
	// for(int i = 1;i <= n;i++){
	// 	for(int j = 1;j <= m;j++){
	// 		cout << vis[i][j] << " ";
	// 	}
	// 	cout << "\n";
	// }
	int maxx = 0;
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= m;j++){
			int cnt = dfs(i,j);
			maxx = max(cnt,maxx);
		}
	}
	cout << maxx << "\n";
}

D – 全球变暖

题目：

Description

你有一张某海域 N × N 像素的照片，. 表示海洋、 # 表示陆地，如下所示：…….
.##….
.##….
….##.
..####.
…###.
…….

其中 “上下左右” 四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有 2 座岛屿。

由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻（上下左右四个相邻像素中有海洋），它就会被淹没。

例如上图中的海域未来会变成如下样子：…….
…….
…….
…….
….#..
…….
…….

请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。

Input

第一行包含一个整数N。(1≤N≤1000)。

以下 N 行 N 列代表一张海域照片。

照片保证第 1行、第 1 列、第N行、第N列的像素都是海洋。

Output

一个整数表示答案。

nenu寒假搜索练习 – Virtual Judge (vjudge.net)

思路：

这道题一开始我想到的解法是，先统计一次原始岛屿个数，然后把会淹没的陆地删掉，再统计一次。然后两次统计相减得到结果。但是交上去之后WA了。所以我考虑到这么一种情况：

7
.......
.##.##.
.#####.
.##.##.
.......
.......
.......

类似这样的图，原本一个岛屿，最后会变成两个岛屿，我的答案就会跑出负数来。

所以我们应该换一个思路想。就是我们在原有统计岛屿个数的基础上，看看这个岛屿上有没有不会被淹没的部分，如果有，说明这个连通岛屿最后不会全部被淹没。

所以我就在dfs里加了个变量判断，如果有，就cnt2++。

最后把 岛屿个数cnt – 不会被淹没的岛屿个数cnt2 就能得出正确的结果了。

代码DFS（AC）：

#include<bits/stdc++.h>
using namespace std;
int mx[1005][1005];
int mx2[1005][1005];
int dx[] = {1,-1,0};
int dy[] = {1,-1,0};
int vis[1005][1005];
int n;
int f;
int check(int x,int y){
    //上下左右都是岛
    if(mx[x - 1][y] && mx[x + 1][y] && mx[x][y - 1] && mx[x][y + 1]){
        return 1;
    }
    return 0;
}
int dfs(int x,int y){
    
    if(!vis[x][y]) f += check(x,y);
    vis[x][y] = 1;
    if(x <= 0 || y <= 0 || x > n || y > n || mx2[x][y] == 0){
        return 0;
    }
    mx2[x][y] = 0;
    return 1 + dfs(x - 1,y) + dfs(x + 1,y) + dfs(x,y + 1) + dfs(x,y - 1);
}
int main(){

    cin >> n;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= n;j++){
            char c;
            cin >> c;
            if(c == '.') mx[i][j] = 0;
            else mx[i][j] = 1;
            mx2[i][j] = mx[i][j];
        }
    }
    int cnt = 0;
    int cnt2 = 0;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= n;j++){
            if(dfs(i,j) > 0){
                cnt++;
                if(f){
                    f = 0;
                    cnt2++;
                }
            }
        }
    }
    cout << cnt - cnt2 << "\n";
}

E – 迷宫寻路

题目：

Description

机器猫被困在一个矩形迷宫里。

迷宫可以视为一个 n×m 矩阵，每个位置要么是空地，要么是墙。机器猫只能从一个空地走到其上、下、左、右的空地。

机器猫初始时位于(1,1)的位置，问能否走到(n,m)位置。

Input

第一行，两个正整数n,m。

接下来n行，输入这个迷宫。每行输入一个长为m的字符串，# 表示墙，. 表示空地。

Output

仅一行，一个字符串。如果机器猫能走到(n,m)，则输出 Yes；否则输出 No。

对于 100% 的数据，保证 1≤n,m≤100，且(1,1)和(n,m)均为空地。

nenu寒假搜索练习 – Virtual Judge (vjudge.net)

思路：

看到题目就马上想到搜索，数据量不大，可以尝试用dfs，因为每个格子也只会被走一次。结束条件就是走到终点的时候，如果能走到的地方走完都没有到达过终点，说明不可到达，输出No，否则就是Yes，用一个全局变量存储判断结果就行。

代码DFS（AC）：

#include<bits/stdc++.h>
using namespace std;
int n,m;
int mx[105][105];
int flag;
int mv[][2] = {{0,1},{1,0},{-1,0},{0,-1}};
void dfs(int x,int y){
    if(x == n && y == m){
        flag = 1;
        return ;
    }
    for(int i = 0;i < 4;i++){
        int xx = x + mv[i][0];
        int yy = y + mv[i][1];
        if(xx <= 0 || y <= 0 || xx > n || yy > m || mx[xx][yy] == 0){
            continue;
        }
        mx[xx][yy] = 0;
        dfs(xx,yy);
    }
}
int main(){
    cin >> n >> m;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            char c;
            cin >> c;
            if(c == '.') mx[i][j] = 1;
            else mx[i][j] = 0;
        }
    }
    dfs(1,1);
    if(flag) cout << "Yes" << "\n";
    else cout << "No" << "\n";
}

总结

这套题基本上就是DFS和BFS的经典题目，思路都较为简单，代码量适中。搜索问题有以下几步：

  1. 判断数据范围，看看用DFS合适还是BFS合适
  2. 能用DFS的就写DFS，因为代码更容易实现一些，缺点在于不易debug
  3. DFS的思想就是先写出结束/终止条件，然后开始各个方向搜索
  4. BFS的思想就是我拓展了什么节点，就把拓展的节点加入队列，然后再依次pop出来处理
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																				
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇