2024/1/16 DFS BFS

目录

走迷宫

find the multipul

走迷宫

844. 走迷宫 - AcWing题库

要求从起点到终点的最短路，首先读入数据

建立一个结构体类型的队列，里面分别存放行，列，最短路的步数（r,c,step) 初始的时候起点和0步数入队列?

分别搜索四个方向，如果不越界且是0那么代表可以走，入队列，步数+1

完整代码

#include <bits/stdc++.h>
struct node
{
    int r,c,step;//依次为行，列，最短路的步数
};
const int N = 110;
int g[N][N];
bool vis[N][N]{};
int rr[4]={-1,1,0,0};
int cc[4]={0,0,-1,1};
int n,m,ans=0;
void bfs()
{
    std::queue<node> q;//建立一个结构体类型的队列
    q.push({1,1,0});
    while(!q.empty())
    {
        node tmp=q.front();
        q.pop();
        int cur_r=tmp.r,cur_c=tmp.c;
        if(cur_r==n&&cur_c==m)
        {
            std::cout<<tmp.step;
            return;
        }
        for(int i = 0;i < 4;i ++)
        {
            int next_r=cur_r+rr[i];
            int next_c=cur_c+cc[i];
            if(next_r>=1&&next_r<=n&&next_c>=1&&next_c<=m&&g[next_r][next_c]==0&&vis[next_r][next_c]==false)
            {
                q.push({next_r,next_c,tmp.step+1});
                vis[next_r][next_c]=true;
            }
        }
    }
}
int main()
{
    std::cin >> n >> m;
    for(int i = 1;i <= n;i ++)
    {
        for(int j = 1;j <= m;j ++)
        {
            std::cin >> g[i][j];
        }
    }
    bfs();
    return 0;
}

find the multipul

1426 -- Find The Multiple (poj.org)

搜索技术 [Cloned] - Virtual Judge (vjudge.net)

要求输出的只含有01的数字是n的倍数

思路：从1开始，*10或*10+1的放入队列判断，如果符合条件则输出，不符合则继续搜索

完整代码

//#include <bits/stdc++.h>
#include <iostream>
#include <queue>
#define int long long
int n;
void bfs()
{
    std::queue<int> q;
    q.push(1);
    while(!q.empty())
    {
        int m=q.front();
        q.pop();
        if(m%n==0)
        {
            std::cout<<m<<"\n";
            break;
        }
        q.push(10*m);
        q.push(10*m+1);
    }
}
signed main()
{
    while(std::cin >> n)
    {
        if(n==0)
            break;
        else
        {
            bfs();
        }
    }
    return 0;
}