devbox
小小林熬夜学编程
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【c++】《搜索习题集》题解，更新至DFS之搜索顺序_c++算法 搜索题目

作者：小小林熬夜学编程 | 2024-05-20 06:47:34

赞

踩

c++算法 搜索题目

目录

Ⅰ. Flood Fill

1097. 池塘计数

题目链接：池塘计数
题目描述
给定一个NXM的农田，雨水用 “W” 表示，如果不是则 “.”，每组相连的积水单元格集合可以看作是一片池塘。
每个单元格视为与其上、下、左、右、左上、右上、左下、右下八个邻近单元格相连。
请你输出共有多少片池塘，即矩阵中共有多少片相连的”W”块。
题目分析
模板题，dfs和bfs都可以解
CODE(BFS)

#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
const int N = 1010;
typedef pair<int, int>PII;
int n, m;
char g[N][N];
bool st[N][N];
int dx[8] = { -1,-1,-1,0,0,1,1,1 };
int dy[8] = { -1,0,1,-1,1,-1,0,1 };
void bfs(int sx, int sy)
{
	queue<PII>q;
	q.push({ sx, sy });
	st[sx][sy] = true;
	while (q.size())
	{
		auto t = q.front();
		q.pop();
		for (int i = 0; i < 8; i++)
		{
			int a = dx[i] + t.x;
			int b = dy[i] + t.y;
			if (a >= 0 && a < n && b >= 0 && b < m && !st[a][b] && g[a][b] == 'W')
			{
				q.push({ a,b });
				st[a][b] = true;
			}
		}
	}
}
int main()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++)cin >> g[i];
	int cnt = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (!st[i][j] && g[i][j] == 'W')
			{
				bfs(i, j);
				cnt++;
			}
		}
	}
	cout << cnt << endl;
	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

CODE(DFS)

#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
const int N = 1010;
typedef pair<int, int>PII;
int n, m;
char g[N][N];
int dx[8] = { -1,-1,-1,0,0,1,1,1 };
int dy[8] = { -1,0,1,-1,1,-1,0,1 };
void dfs(int sx, int sy)
{
	g[sx][sy] = '.';
	for (int i = 0; i < 8; i++)
	{
		int a = sx + dx[i], b = sy + dy[i];
		if (a >= 0 && a < n && b >= 0 && b < m && g[a][b] == 'W')
			dfs(a, b);
	}
}
int main()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++)cin >> g[i];
	int cnt = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (g[i][j] == 'W')
			{
				dfs(i, j);
				cnt++;
			}
		}
	}
	cout << cnt << endl;
	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

1098. 城堡问题

题目链接：城堡问题
题目描述
给定一个城堡地形图，计算城堡一共多少个房间，最大房间有多大
在这里插入图片描述
特征P 来描述，我们用1表示西墙，2表示北墙，4表示东墙，8表示南墙，P 为该方块包含墙的数字之和。

例如，如果一个方块的 P 为3，则 3 = 1 + 2，该方块包含西墙和北墙。
题目分析
在这里插入图片描述
在这里插入图片描述

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N=50;
typedef pair<int,int>PII;
queue<PII>q;
int g[N][N];
bool st[N][N];
int dx[4]={0,-1,0,1};
int dy[4]={-1,0,1,0};

int n,m;
int bfs(int sx,int sy)
{
    q.push({sx,sy});
    st[sx][sy]=true;
    int area=0;
    while(q.size())
    {
        auto t=q.front();
        q.pop();
        area++;
        for(int i=0;i<4;i++)
        {
            int a=dx[i]+t.x;
            int b=dy[i]+t.y;
            if(a>=0&&a<n&&b>=0&&b<m&&!st[a][b]&&!(g[t.x][t.y]>>i&1))
            { 
                q.push({a,b});
                st[a][b]=true;
            }
        }
    }
    return area;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            scanf("%d",&g[i][j]);
    int res=0,maxv=0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(!st[i][j])
            {
                res++;
                maxv=max(maxv,bfs(i,j));
            }
        }
    }
    printf("%d\n",res);
    printf("%d\n",maxv);
    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

1106. 山峰和山谷

题目链接：山峰和山谷
题目描述

  1. 没有比他高的叫山峰
  2. 没有比它矮的叫山谷
  3. 还存在又比它高，又比它矮的不算山峰和山谷

在这里插入图片描述
在这里插入图片描述
题目分析
具体看代码
CODE

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int,int>PII;
const int N=1010;
int dx[8]={-1,-1,-1,0,0,1,1,1};
int dy[8]={-1,0,1,1,-1,1,0,-1};
int n;
int h[N][N];
bool st[N][N];
void bfs(int sx,int sy,bool&has_higher,bool&has_lower)
{
    queue<PII>q;
    st[sx][sy]=true;
    q.push({sx,sy});
    while(q.size())
    {
        auto t=q.front();
        q.pop();
        for(int i=0;i<8;i++)
        {
            int a=dx[i]+t.x;
            int b=dy[i]+t.y;
            if(a<0||a>=n||b<0||b>=n)continue;
            if(h[a][b]!=h[t.x][t.y])
            {
                if(h[a][b]>h[t.x][t.y])has_higher=true;
                else has_lower=true;
            }
            else if(!st[a][b])
            {
                q.push({a,b});
                st[a][b]=true;
            }
        }
    }
}
int main()
{

    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        cin>>h[i][j];
    int peak=0,valley=0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(!st[i][j])
            {
                bool has_higher=false,has_lower=false;
                bfs(i,j,has_higher,has_lower);
                if(!has_higher)peak++;
                if(!has_lower)valley++;
            }
        }
    }
    cout<<peak<<" "<<valley<<endl;
    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

Ⅱ. 最短路模型

1076. 迷宫问题

题目链接：迷宫问题
题目描述
1 表示墙壁， 0 表示路
从左上角走到右下角，并输出最短路径
题目分析
倒着走，存前驱
CODE

#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
const int N = 1010;
typedef pair<int, int>PII;
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
PII pre[N][N];
int g[N][N];
bool st[N][N];
int n;
void bfs()
{
	queue<PII>q;
	q.push({ n - 1,n - 1 });
	st[n - 1][n - 1] = true;
	while (q.size())
	{
		auto t = q.front();
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int a = t.x + dx[i];
			int b = t.y + dy[i];
			if (a >= 0 && a < n && b >= 0 && b < n && g[a][b] == 0 && !st[a][b])
			{
				q.push({ a,b });
				st[a][b] = true;
				pre[a][b] = t;
			}
		}
	}
	int l = 0, r = 0;
	while (!(l==n-1&&r==n-1))
	{
		cout << l << ' ' << r << endl;
		auto t = pre[l][r];
		l = t.x, r = t.y;
	}
	cout << n - 1 << ' ' << n - 1 << endl;
}
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> g[i][j];
	bfs();
	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

188. 武士风度的牛

题目链接：武士风度的牛
题目描述
从K 到 H，障碍物是 *
在这里插入图片描述
题目分析
具体看代码，大同小异

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N = 155;
typedef pair<int, int>PII;
int dx[] = { -2, -1, 1, 2, 2, 1, -1, -2 };
int dy[] = { 1, 2, 2, 1, -1, -2, -2, -1 };
int n, m;
char g[N][N];
int dist[N][N];
int bfs(PII start, PII end)
{
	memset(dist, -1, sizeof dist);
	queue<PII>q;
	q.push(start);
	dist[start.x][start.y] = 0;
	while (q.size())
	{
		auto t = q.front();
		q.pop();
		for (int i = 0; i < 8; i++)
		{
			int a = t.x + dx[i];
			int b = t.y + dy[i];
			if (a < 0 || a >= n || b < 0 || b >= m || dist[a][b] != -1 || g[a][b] == '*')continue;
			dist[a][b] = dist[t.x][t.y] + 1;
			if (end == make_pair(a, b))return dist[a][b];
			q.push({ a,b });
		}
	}
}
int main()
{
	cin >> m >> n;
	for (int i = 0; i < n; i++)
		cin >> g[i];
	PII start, end;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (g[i][j] == 'H')end = { i,j };
			if (g[i][j] == 'K')start = { i,j };
		}
	}
	cout << bfs(start, end) << endl;
	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

1100. 抓住那头牛

题目链接：抓住那头牛
题目描述
农夫和牛都位于数轴上，农夫起始位于点 N，牛位于点 K。
从 X 移动到 X−1 或 X+1，每次移动花费一分钟
从 X 移动到 2∗X，每次移动花费一分钟
农夫最少要花多少时间才能抓住牛？
题目分析
一维BFS
CODE

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, k;
queue<int>q;
int dist[N];
int bfs()
{
	memset(dist, -1, sizeof dist);
	dist[n] = 0;
	q.push(n);
	while (q.size())
	{
		auto t = q.front();
		q.pop();
		if (t == k)return dist[k];
		if (t + 1 <= k && dist[t + 1] == -1)
		{
			dist[t + 1] = dist[t] + 1;
			q.push(t + 1);
		}
		if (t - 1 >= 0 && dist[t - 1] == -1)
		{
			dist[t - 1] = dist[t] + 1;
			q.push(t - 1);
		}
		if (t * 2 < N && dist[t * 2] == -1)
		{
			dist[t * 2] = dist[t] + 1;
			q.push(t * 2);
		}
	}
	return -1;
}
int main()
{
	cin >> n >> k;
	cout << bfs() << endl;
	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

Ⅲ. 多源BFS

173. 矩阵距离

题目链接：矩阵距离
题目描述
求矩阵每一行 0 到 1 的距离
题目分析
多源BFS
CODE

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N=1010;
int n,m;
char g[N][N];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
typedef pair<int,int>PII;
int dist[N][N];
void bfs()
{
    queue<PII>q;
    memset(dist,-1,sizeof dist);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(g[i][j]=='1')
            {
                dist[i][j]=0;
                q.push({i,j});
            }
        }
    }
    while(q.size())
    {
        auto t=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            int a=t.x+dx[i];
            int b=t.y+dy[i];
            if(a<0||a>=n||b<0||b>=m)continue;
            if(dist[a][b]!=-1)continue;
            dist[a][b]=dist[t.x][t.y]+1;
            q.push({a,b});
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
        cin>>g[i];
    bfs();
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
            cout<<dist[i][j]<<" ";
        cout<<endl;
    }
    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

Ⅳ. 最小步数模型

1107. 魔板

题目链接：魔板
题目描述
给定一个8个大小相同的格子的魔板

1 2 3 4
8 7 6 5

  • 1
  • 2

这里提供三种基本操作，分别用大写字母 A，B，C 来表示（可以通过这些操作改变魔板的状态）：

A：交换上下两行；
B：将最右边的一列插入到最左边；
C：魔板中央对的4个数作顺时针旋转。
输入目标状态，求最短的操作序列
题目分析
最小操作序列—>bfs
逆序求路径---->存前驱---->正序输出前驱
正序求路径同理，最后reverse即可

#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
char g[2][4];
unordered_map<string, pair<char, string>>pre;
unordered_map<string, int>dist;
void t_set(string state)
{
	for (int i = 0; i < 4; i++)g[0][i] = state[i];
	for (int i = 7, j = 0; j < 4; i--, j++)g[1][j] = state[i];
}
string t_get()
{
	string res;
	for (int i = 0; i < 4; i++)res += g[0][i];
	for (int i = 3; i >= 0; i--)res += g[1][i];
	return res;
}
string move0(string state)
{
	t_set(state);
	for (int i = 0; i < 4; i++)swap(g[0][i], g[1][i]);
	return t_get();
}
string move1(string state)
{
	t_set(state);
	int v0 = g[0][3], v1 = g[1][3];
	for (int i = 3; i >= 0; i--)
	{
		g[0][i] = g[0][i - 1];
		g[1][i] = g[1][i - 1];
	}
	g[0][0] = v0, g[1][0] = v1;
	return t_get();
}
string move2(string state)
{
	t_set(state);
	int v0 = g[0][1];
	int v1 = g[0][2];
	int v2 = g[1][1];
	int v3 = g[1][2];
	g[0][1] = v2;
	g[0][2] = v0;
	g[1][1] = v3;
	g[1][2] = v1;
	return t_get();
}
int bfs(string start, string end)
{
	if (start == end)return 0;
	queue<string>q;
	q.push(start);
	dist[start] = 0;
	while (q.size())
	{
		auto t = q.front();
		q.pop();
		string m[3];
		m[0] = move0(t);
		m[1] = move1(t);
		m[2] = move2(t);
		for (int i = 0; i < 3; i++)
		{
			if (!dist[m[i]])
			{
				dist[m[i]] = dist[t] + 1;
				pre[m[i]] = { 'A' + i,t };
				q.push(m[i]);
				if (m[i] == end)return dist[end];
			}
		}
	}
	return -1;
}
int main()
{
	int x;
	string start, end;
	for (int i = 0; i < 8; i++)
	{
		cin >> x;
		end += char(x + '0');
	}
	for (int i = 1; i <= 8; i++)start += char('0' + i);
	int step = bfs(start, end);
	cout << step << endl;
	string res;
	while (end != start)
	{
		res += pre[end].first;
		end = pre[end].second;
	}
	reverse(res.begin(), res.end());
	if (step > 0)cout << res << endl;
	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

Ⅴ. 双端队列广搜

175. 电路维修

题目链接：电路维修
题目描述
在这里插入图片描述
每个格点都是电线的接点，每个格子都包含一个电子元件。
电子元件的主要部分是一个可旋转的、连接一条对角线上的两个接点的短电缆。
在旋转之后，它就可以连接另一条对角线的两个接点。
电路板左上角的接点接入直流电源，右下角的接点接入飞行车的发动装置。
注意：只能走斜向的线段，水平和竖直线段不能走
题目分析
双端队列BFS
为什么这道题不能用普通bfs呢，普通bfs在更新一次点后就不会在继续更新，此题有权值为0的点，因此不能用普通bfs，更类似于dijkstra的堆优化版本
参考：https://www.acwing.com/solution/content/21775/
在这里插入图片描述
在代码中此处体现，即每次出队的距离才是真正的距离
在这里插入图片描述

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int, int>PII;
const int N = 510, M = N * N;
int dx[4] = { -1,-1,1,1 };
int dy[4] = { -1,1,1,-1 };
int ix[4] = { -1,-1,0,0 };
int iy[4] = { -1,0,0,-1 };
char cs[] = "\\/\\/";
int n, m;
char g[N][N];
int dist[N][N];
bool st[N][N];
int bfs()
{
	memset(dist, 0x3f, sizeof dist);
	memset(st, 0, sizeof st);
	dist[0][0] = 0;
	deque<PII>q;
	q.push_back({ 0,0 });
	while (q.size())
	{
		auto t = q.front();
		q.pop_front();
		if (st[t.x][t.y])continue;
		st[t.x][t.y] = true;
		for (int i = 0; i < 4; i++)
		{
			int a = t.x + dx[i], b = t.y + dy[i];
			if (a<0 || a>n || b<0 || b>m)continue;
			int ca = t.x + ix[i], cb = t.y + iy[i];
			int d = dist[t.x][t.y] + (g[ca][cb] != cs[i]);
			if (d < dist[a][b])
			{
				dist[a][b] = d;
				if (g[ca][cb] != cs[i])q.push_back({ a,b });
				else q.push_front({ a,b });
			}
		}
	}
	return dist[n][m];
}
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		cin >> n >> m;
		for (int i = 0; i < n; i++)cin >> g[i];
		int t = bfs();
		if (t == 0x3f3f3f3f)puts("NO SOLUTION");
		else printf("%d\n", t);
	}
	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

Ⅵ . 双向广搜

190. 字串变换

题目链接：字串变换
题目描述
给定一系列规则。将一个字符串转换成另一个字符串
题目描述
双端广搜每一次扩展一层
参考：https://www.acwing.com/activity/content/code/content/132167/

#include <bits/stdc++.h>
#include <unordered_map>      
using namespace std;
const int N = 6;
string A, B;
string a[N], b[N];
int n;
int extend(queue<string>& q, unordered_map<string, int>& da, unordered_map<string, int>& db,string a[N], string b[N])
{
	int d = da[q.front()];
	while (q.size()&&d==da[q.front()])//处理同一层
	{
		auto t = q.front();
		q.pop();
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < t.size(); j++)
			{
				if (t.substr(j, a[i].size()) == a[i])
				{
					string r = t.substr(0, j) + b[i] + t.substr(j + a[i].size());
					if (db.count(r))return da[t] + 1 + db[r];
					if (da.count(r))continue;
					da[r] = da[t] + 1;
					q.push(r);
				}
			}
		}
	}
	return 11;
}
int bfs()
{
	if (A == B)return 0;
	queue<string>qa, qb;
	unordered_map<string, int>da, db;
	qa.push(A), qb.push(B);
	da[A] = 0, db[B] = 0;
	while (qa.size() && qb.size())
	{
		int t;
		if (qa.size() < qb.size())t = extend(qa, da, db, a, b);
		else t = extend(qb, db, da, b, a);
		if (t <= 10)return t;
	}
	return -1;
}
int main()
{
	cin >> A >> B;
	while (cin >> a[n] >> b[n])n++;
	int t = bfs();
	if (t == -1)puts("NO ANSWER!");
	else cout << t << endl;
	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

Ⅶ . Astar

178. 第K短路

题目链接：第K短路
题目描述
给定一张 N 个点（编号 1,2…N），M 条边的有向图，求从起点 S 到终点 T 的第 K 短路的长度，路径允许重复经过点或边。
求第K条短路
题目分析
终点第K次出队为第K条最短路
CODE

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N = 1010, M = 200010;
typedef pair<int, int>PII;
typedef pair<int, pair<int, int>>PIII;
int n, m, s, T, K;
int h[N], rh[N], e[M], ne[M], w[M], idx;
int dist[N], cnt[N];
bool st[N];
void add(int h[N], int a, int b, int c)
{
	e[idx] = b;
	w[idx] = c;
	ne[idx] = h[a];
	h[a] = idx++;
}
void dijkstra()
{
	priority_queue<PII, vector<PII>, greater<PII>>heap;
	heap.push({ 0,T });
	memset(dist, 0x3f, sizeof dist);
	dist[T] = 0;
	while (heap.size())
	{
		auto t = heap.top();
		heap.pop();
		int ver = t.y;
		if (st[ver])continue;
		st[ver] = true;
		for (int i = rh[ver]; ~i; i = ne[i])
		{
			int j = e[i];
			if (dist[j] > dist[ver] + w[i])
			{
				dist[j] = dist[ver] + w[i];
				heap.push({ dist[j],j });
			}
		}
	}
}
int astar()
{
	priority_queue<PIII, vector<PIII>, greater<PIII>>heap;
	heap.push({ dist[s],{0,s} });//估价,真实，点
	while (heap.size())
	{
		auto t = heap.top();
		heap.pop();
		int ver = t.y.y, distance = t.y.x;
		cnt[ver]++;
		if (cnt[T] == K)return distance;
		for (int i = h[ver]; ~i; i = ne[i])
		{
			int j = e[i];
			if(cnt[j] < K)
			heap.push({ distance + dist[j] + w[i], {distance + w[i],j} });
		}
	}
	return -1;
}
int main()
{
	cin >> m >> n;
	memset(h, -1, sizeof h);
	memset(rh, -1, sizeof rh);
	for (int i = 0; i < n; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		add(h, a, b, c);
		add(rh, b, a, c);
	}
	cin >> s >> T >> K;
	if (s == T)K++;
	dijkstra();
	cout << astar();
	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

Ⅷ . DFS之连通性模型

1112. 迷宫

题目链接：迷宫
CODE

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n;
char g[N][N];
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
bool st[N][N];
int xa, xb, ya, yb;
bool dfs(int x, int y)
{
	if (g[x][y] == '#')return false;
	if (x == xb && y == yb)return true;
	st[x][y] = true;
	for (int i = 0; i < 4; i++)
	{
		int a = x + dx[i];
		int b = y + dy[i];
		if (st[a][b])continue;
		if (a < 0 || a >= n || b < 0 || b >= n)continue;
		if (dfs(a, b))return true;
	}
	return false;
}
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		cin >> n;
		for (int i = 0; i < n; i++)cin >> g[i];
		cin >> xa >> ya >> xb >> yb;
		memset(st, 0, sizeof st);
		if (dfs(xa, ya))puts("YES");
		else puts("NO");
	}
	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

1113. 红与黑

题目链接：红与黑
CODE(BFS)

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int, int>PII;
const int N = 30;
char g[N][N];
int n, m;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
bool st[N][N];
int bfs(int x,int y)
{
	int cnt = 0;
	queue<PII>q;
	q.push({ x,y });
	st[x][y] = true;
	while (q.size())
	{
		auto t = q.front();
		q.pop();
		cnt++;
		for (int i = 0; i < 4; i++)
		{
			int a = dx[i] + t.x;
			int b = dy[i] + t.y;
			if (a < 0 || a >= n || b < 0 || b >= m)continue;
			if (st[a][b])continue;
			if (g[a][b] != '.')continue;
			st[a][b] = true;
			q.push({ a,b });
		}
	}
	return cnt;
}
int main()
{
	while (cin >> m >> n, n || m)
	{
		memset(st, 0, sizeof st);
		for (int i = 0; i < n; i++)cin >> g[i];
		int x, y, f = 0;
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if (g[i][j] == '@')
				{
					f = 1;
					x = i, y = j;
				}
			}
			if (f)break;
		}
		cout << bfs(x, y) << endl;
	}
	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

CODE(DFS)

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int, int>PII;
const int N = 30;
char g[N][N];
int n, m;
int cnt;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
bool st[N][N];
void dfs(int x,int y)
{
	st[x][y] = true;
	cnt ++;
	for (int i = 0; i < 4; i++)
	{
		int a = x + dx[i], b = y + dy[i];
		if (a < 0 || a >= n || b < 0 || b >= m || st[a][b]|| g[a][b] != '.')continue;
		dfs(a, b);
	}
}
int main()
{
	while (cin >> m >> n, n || m)
	{
	    cnt = 0;
		memset(st, 0, sizeof st);
		for (int i = 0; i < n; i++)cin >> g[i];
		int x, y, f = 0;
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if (g[i][j] == '@')
				{
					f = 1;
					x = i, y = j;
				}
			}
			if (f)break;
		}
		dfs(x, y);
		cout<< cnt <<endl;
	}
	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

Ⅸ . DFS之搜索顺序

1116. 马走日

题目链接：马走日
CODE

#include <bits/stdc++.h>
using namespace std;
const int N = 10;
int dx[] = { -2,-2,-1,1,2,2,1,-1 };
int dy[] = { -1,1,2,2,1,-1,-2,-2 };
int n, m, sx, sy;
int t;
int g[N][N];
bool st[N][N];
int cnt;
int ans;
void dfs(int sx, int sy, int cnt)
{
	st[sx][sy] = true;
	if (cnt == n * m)
	{
		ans++;
		return;
	}
	for (int i = 0; i < 8; i++)
	{
		int a = dx[i] + sx;
		int b = dy[i] + sy;
		if (a < 0 || a >= n || b < 0 || b >= m || st[a][b])continue;
		dfs(a, b, cnt + 1);
		st[a][b] = false;
	}
}
int main()
{
	cin >> t;
	while (t--)
	{
		cin >> n >> m >> sx >> sy;
		ans = 0;
		memset(st, 0, sizeof st);
		dfs(sx, sy, 1);
		cout << ans << endl;
	}
	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

1117. 单词接龙

题目链接：单词接龙
CODE

#include <bits/stdc++.h>
using namespace std;
const int N = 21;
int n;
string word[N];
int g[N][N];
int used[N];
int ans;
void dfs(string state,int last)
{
	ans = max((int)state.size(), ans);
	used[last]++;
	for (int i = 0; i < n; i++)
		if (g[last][i] && used[i] < 2)
			dfs(state + word[i].substr(g[last][i]), i);
		used[last]--;
}
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)cin >> word[i];
	char start;
	cin >> start;
	for(int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
		{
			string a = word[i];
			string b = word[j];
			for (int k = 1; k < min(a.size(), b.size()); k++)
			{
				if (a.substr(a.size() - k, k) == b.substr(0, k))
				{
					g[i][j] = k;
					break;
				}
			}
		}
	for (int i = 0; i < n; i++)
	{
		if (word[i][0] == start)
			dfs(word[i], i);
	}
	cout << ans << endl;
	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
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/596590
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号