搜索题解

本篇文章对一些搜索题目进行摘录。

赵子龙七进七出

原题链接

题目描述

分析

每隔三条边才能算作跳一步过去，一开始的想法是重新建图，利用最短路求解。但是重新建图并不方便，由于问最少前进步数，所以可以直接$bfs$.设置数组$mark[s][step]$,表示到点$s$时是隔了几步，对$s$的邻接点进行遍历，$step$变成$(step+1)\pmod 3$.最后判断是否走到了终点，如果走到，步数除以$3$即可。

代码

展开查看 >folded

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <unordered_map>

#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int,int> PI;
const int maxn = 1e5+10;
const ll mod = 1e9+7;

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
int n,m;
int s,t;
vector<int>g[maxn];
int mark[maxn][3];  //第走到这个点是哪步
int dp[maxn][3];    //走了多少步

void bfs()
{
    queue<PI> q;
    q.push(PI(s,0));
    mark[s][0] = 1; //第0步走到的点才是能跳到的点
    dp[s][0] = 0;  //初始步数为0
    while(!q.empty()) 
    {
        PI now = q.front();
        q.pop();
        int u = now.first,step = now.second;
        for(auto v:g[u])
        {
            int ss = (step+1)%3;
            if(mark[v][ss]==0)
            {
                mark[v][ss] = 1;  //设置标记
                dp[v][ss] = dp[u][step]+1; //步数加1
                q.push(PI(v,ss));
            }
        }
    }
}

int main()
{
    cin>>n>>m;
    while(m--)
    {
        int u,v;
        u = read(),v = read();
        g[u].push_back(v);
    }
    cin>>s>>t;
    bfs();
    if(mark[t][0]==0)
    {
        cout<<-1<<endl;
        return 0;
    }
    cout<<dp[t][0]/3; //第0步走到，步数除以三即可
    return 0;
}