本文整理了 ED_Builder 在初学搜索算法时做的题目

DFS

P1219 八皇后

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<bits/stdc++.h>
using namespace std;
int n,a[20],ans;//共计 n 个皇后,可行的答案存放在 a 数组中,共有 ans 种答案
bool vis_lie[30],vis_l[30],vis_r[30];//记录当前列(|),左斜(/),右斜(\)是否被访问
void print()//输出答案
{
    if(ans>3)  return;//由题可得,只需要输出 3 种排列
    for(int i=1;i<=n;i++)  cout<<a[i]<<' ';
    cout<<endl;
    return;
}
void dfs(int x)//形参 x :当前是第 x 个皇后
{
    if(x>n)//一种可行的方案达成
    {
        ans++;//方案数++
        print();//输出答案
        return;
    }
    for(int i=1;i<=n;i++)//枚举所有答案
    {
        if(!vis_lie[i]&&!vis_l[x-i+n]&&!vis_r[x+i])//是否被访问过(规律见 L40 )
        {
            vis_lie[i]=true,vis_l[x-i+n]=true,vis_r[x+i]=true;//标记
            a[x]=i;//存答案
            dfs(x+1);//继续递归
            vis_lie[i]=false,vis_l[x-i+n]=false,vis_r[x+i]=false;//回溯
        }
    }
}
int main()
{
    cin>>n;
    dfs(1);
    cout<<ans;
    return 0;
}

/*
对于 vis_l[x-i+n] : 画图可得,位于同一个左斜线的坐标, x+y 都相等, +n 防止越下界
对于 vis_r[x+i] : 画图可得,位于同一个右斜线的坐标, abs(x-y) 都相等
*/

P1706 全排列问题

P1 - 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
#include<bits/stdc++.h>
using namespace std;
int n,a[20];//枚举 n 个数字,可行的答案存放在 a 中
bool vis[20];//已经被访问过的
void print()//输出答案
{
    for(int i=1;i<=n;i++)  cout<<setw(5)<<a[i];
    cout<<endl;
    return;
}
void dfs(int x)
{
    if(x>n)//已经有了一个方案
    {
        print();
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])//没被访问
        {
            a[x]=i;//记录答案
            vis[i]=true;//标记
            dfs(x+1);//继续递归
            vis[i]=false;//回溯
        }
    }
}
int main()
{
    cin>>n;
    dfs(1);//从 1 开始
    return 0;
}

P2 - 枚举优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int num[n];
    for(int i=1;i<=n;i++)  num[i]=i;
    do
    {
        for(int i=1;i<=n;i++)  cout<<setw(5)<<num[i];
        cout<<endl;
    }while(next_permutation(num+1,num+1+n));
    return 0;
}

P1605 迷宫

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
#include<iostream>
#include<cstring>//这里不用万能头是因为想用 map 当变量名
using namespace std;
int n,m,t,sx,sy,fx,fy,ans;
//地图长宽,障碍数量,起点坐标,终点坐标,答案
int dx[5]={1,0,-1,0},dy[5]={0,-1,0,1};//位移
bool map[10][10];//地图
void dfs(int x,int y)
{
    if(x==fx&&y==fy)//到达终点
    {
        ans++;
        return;
    }
    for(int i=0;i<4;i++)//枚举位移
    {
        int tmp_x=dx[i]+x,tmp_y=dy[i]+y;//移动
        if(tmp_x>=1&&tmp_x<=n&&tmp_y>=1&&tmp_y<=m&&map[tmp_x][tmp_y])
        //合法判断:坐标未越界,位置可用(没有障碍且没被访问)
        {
            map[tmp_x][tmp_y]=false;//标记访问
            dfs(tmp_x,tmp_y);//继续递归
            map[tmp_x][tmp_y]=true;//回溯
        }
    }
}
int main()
{
    memset(map,true,sizeof(map));//初始化
    cin>>n>>m>>t>>sx>>sy>>fx>>fy;
    for(int i=1;i<=t;i++)//读入障碍
    {
        int x,y;
        cin>>x>>y;
        map[x][y]=false;//不能走
    }
    map[sx][sy]=false;//byd就是这个东西没加 WA 了 3 个点:起点永远被访问!
    dfs(sx,sy);
    cout<<ans;
    return 0;
}

P1036 选数

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
#include<bits/stdc++.h>
using namespace std;
int n,k,x[25],ans;//共有 n 个数,要选 k 个数,答案
bool vis[25];//是否已经被选择
bool check_prime(int n)//判断质数
{
    if(n<=1)  return false;
    for(int i=2;i<=sqrt(n);i++)
        if(n%i==0)  return false;
    return true;
}
void dfs(int pos,int cnt,int sum)
{
    if(cnt>=k)//选完了
    {
        if(check_prime(sum))  ans++;//判断质数,然后答案自增
        return;
    }
    for(int i=pos;i<=n;i++)
    {
        if(vis[i])//没被选
        {
            vis[i]=false;//标记
            dfs(i+1,cnt+1,sum+x[i]);//继续递归:下标++ ,选择的数量++ ,总和增加对应下标的数
            vis[i]=true;//回溯
        }
    }
}
int main()
{
    memset(vis,true,sizeof(vis));//初始化
    cin>>n>>k;
    for(int i=1;i<=n;i++)  cin>>x[i];
    dfs(1,0,0);//DFS:下标从 1 开始,已经选了 0 个数,选择的数的总和为 0
    cout<<ans;
    return 0;
}

P1238 走迷宫

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<bits/stdc++.h>
#define int long long
using namespace std;

int m,n;// m 行 n 列 
int mp[20][20],vis[20][20],have_solution=false;//地图,是否被访问,是否有解 
int begin_x,begin_y,end_x,end_y;//起点和终点 
int dx[5]={0,-1,0,1},dy[5]={-1,0,1,0};//偏移
int ans[100000][3],k;
//存放答案:第一维是答案,第二维是 x 和 y 坐标,例如 ans[3][2] 表示第 3 个答案的 y 坐标;k是答案的长度 

void print()//输出一种答案 
{
    if(have_solution==false)  have_solution=true;//更新为有解 
    for(int i=0;i<k;i++)  cout<<'('<<ans[i][1]<<','<<ans[i][2]<<')'<<"->";
    cout<<'('<<end_x<<','<<end_y<<')'<<endl;
    //因为在 L20-41 的 dfs 中,如果到了终点就不会添加答案了,所以还要输出一遍终点的坐标 
}

void dfs(int x,int y)
{
    if(x==end_x&&y==end_y)//到达终点 
    {
        print();//输出答案 
        return;
    }
    for(int i=0;i<4;i++)//枚举偏移 
    {
        int nxt_x=x+dx[i],nxt_y=y+dy[i];//定位下一步 
        if(mp[nxt_x][nxt_y]==1&&vis[nxt_x][nxt_y]==0)
        //下一步可以走并且没被访问 
        {
            vis[x][y]=1;//标记上一步被访问 
            ans[k][1]=x,ans[k][2]=y;//记录可行的一步 
            k++;//增加指针 
            dfs(nxt_x,nxt_y);//继续找下一步 
            vis[x][y]=0;//回溯,设为未访问 
            k--;//倒回去 
        }
    }
}

signed main()
{
    cin>>m>>n;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            cin>>mp[i][j];//读入地图 
    cin>>begin_x>>begin_y>>end_x>>end_y;//读入起点和终点 
    dfs(begin_x,begin_y);
    if(!have_solution)  cout<<-1;//没有解 
    return 0;//结束 :) 
}

BFS

注意: BFS 不能用于加权图,因为 BFS 只会查找边数最少的路径
例如 100 -> 100 和 1 -> 1 -> 1 -> 1
BFS 会选择 100 -> 100

当数据范围较小（ ≤20\le20 ）时，用 DFS 也不是不可以

P1746 离开中山路

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
#include<iostream>
#include<queue>
using namespace std;
struct Point//单个点的坐标
{
    int x,y;
};
int n;
char map[1005][1005];
int dis[1005][1005];//到起点的距离
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};//位移
int start_x,start_y,final_x,final_y;//由题可得,起点和终点
queue<Point> q;//等待处理的点
void bfs(int x,int y)
{
    q.push((Point){x,y});//压入当前点
    dis[x][y]=0;//起点
    while(!q.empty())//只要队列非空
    {
        Point t=q.front();//读取当前队头
        q.pop();//弹出
        for(int i=0;i<4;i++)//枚举位移
        {
            int nxt_x=t.x+dx[i],nxt_y=t.y+dy[i];//下一个点
            if(nxt_x<1||nxt_x>n||nxt_y<1||nxt_y>n||map[nxt_x][nxt_y]=='1'||dis[nxt_x][nxt_y]>0)  continue;
            //判断:越界+有障碍+被访问

            q.push((Point){nxt_x,nxt_y});//压入下一个点
            dis[nxt_x][nxt_y]=dis[t.x][t.y]+1;//增加 1 段距离
        }
    }
    return;
}
int main()
{

    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>map[i][j];
    cin>>start_x>>start_y>>final_x>>final_y;
    bfs(start_x,start_y);
    cout<<dis[final_x][final_y];
    return 0;
}

P1443 马的遍历

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<bits/stdc++.h>
using namespace std;
struct Point//当前马位于的坐标
{
    int x,y;
};
int n,m,x,y,dis[405][405];//棋盘 n 行 m 列,在点 (x,y) 有一个马,当前点 (x,y) 马需要走 dis[x][y] 步
int dx[]={2,1,-2,1,-1,2,-2,-1};
int dy[]={1,2,1,-2,2,-1,-1,-2};//位移
queue<Point> q;//当前需要处理的点
void bfs(int x,int y)
{
    q.push((Point){x,y});//入队处理起点
    dis[x][y]=0;//起点已经有一个马了
    while(!q.empty())
    {
        Point t=q.front();//取队头处理
        q.pop();//弹出
        for(int i=0;i<8;i++)//枚举位移
        {
            int nxt_x=t.x+dx[i],nxt_y=t.y+dy[i];//生成新坐标
            if(nxt_x<1||nxt_x>n||nxt_y<1||nxt_y>m||dis[nxt_x][nxt_y]!=-1)  continue;
            //检查:越界+被访问

            dis[nxt_x][nxt_y]=dis[t.x][t.y]+1;//更新步数为上一个点+1
            q.push((Point){nxt_x,nxt_y});//继续压入新的点继续处理
        }
    }
    return;
}
int main()
{
    memset(dis,-1,sizeof(dis));//初始化
    cin>>n>>m>>x>>y;
    bfs(x,y);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)  cout<<setw(5)<<dis[i][j];
        cout<<endl;
    }
    return 0;
}

P2895 Meteor Shower S

耗时 2 个月的巅峰对决，但最终还是我赢了！

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<bits/stdc++.h>
#define int long long
using namespace std;
const int LEN=305;
struct Point//存储坐标的点 
{
    int x,y;
};
int m;
int mp[LEN][LEN],dis[LEN][LEN];//地图,距离 
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};//偏移 
queue<Point> q;
int bfs()
{
    q.push((Point){0,0});//第一个位置是 (0,0) 
    dis[0][0]=0;//起点 (0,0) 距离当前位置 (0,0) 的距离是 0 
    while(!q.empty())
    {
        Point now=q.front();//找到当前点 
        q.pop();
        for(int d=0;d<4;d++)//枚举偏移 
        {
            int nxt_x=now.x+dx[d],nxt_y=now.y+dy[d];//得到下一个点的位置
            if(nxt_x<0||nxt_y<0)  continue;//越界 
            if(dis[nxt_x][nxt_y])  continue;//被访问
            if(dis[now.x][now.y]+1>=mp[nxt_x][nxt_y])  continue;
            //剪枝: 下一个点已经无法到达: 当前距离 +1 即为到下一个点的距离,然后和下一个点的坠落时间比较
            dis[nxt_x][nxt_y]=dis[now.x][now.y]+1;//更新距离 
            q.push((Point){nxt_x,nxt_y});//压入下一个点 
            if(mp[nxt_x][nxt_y]>1e9)  return dis[nxt_x][nxt_y];//没有流行砸到,答案就是当前点的距离 
        }
    }
    return -1;
}
signed main()
{
    memset(mp,0x3f,sizeof(mp));//初始化一个足够大的数,为了在下面取到最小值 
    cin>>m;
    while(m--)
    {
        int x,y,time;//坐标,流星砸下来的时间 
        cin>>x>>y>>time;
        mp[x][y]=min(mp[x][y],time);//取砸下来的最小值 
        for(int d=0;d<4;d++)//枚举偏移 
        {
            int nxt_x=x+dx[d],nxt_y=y+dy[d];//得到即将蔓延的点 
            if(nxt_x<0||nxt_x>301||nxt_y<0||nxt_y>301)  continue;//越界 
            mp[nxt_x][nxt_y]=min(mp[nxt_x][nxt_y],time);//继续取最小值 
        }
    }
    cout<<bfs();
    exit(0);
}
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

快来参与讨论吧~