搜索+图论1 练习答案+思路

走迷宫

代码

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N=105;

int ans=0x3f3f3f3f;

struct node
{
    int x;
    int y;
    int step;
};

int n,m;

char g[N][N];
bool vis[N][N];

int dx[4]= {-1,1,0,0};
int dy[4]= {0,0,1,-1};

void bfs(int x,int y,int X,int Y)
{
    queue<node> q;

    q.push({x,y,0});

    while(!q.empty())
    {
        node t=q.front();

        if(t.x==X && t.y==Y)
        {
            ans=t.step;
            break;
        }

        q.pop();

        for(int i=0; i<4; i++)
        {
            int tx=t.x+dx[i];
            int ty=t.y+dy[i];

            if(tx<1 || ty<1 || tx>n || ty>m || g[tx][ty]=='0' || vis[tx][ty]) continue;

            vis[tx][ty]=true;
            q.push({tx,ty,t.step+1});

        }
    }

}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>n>>m;

    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            cin>>g[i][j];
        }
    }

    int x1,y1,x2,y2;

    cin>>x1>>y1>>x2>>y2;

    bfs(x1,y1,x2,y2);

    if(ans==0x3f3f3f3f)
    {
        cout<<"-1"<<endl;
    }
    else
    {
        cout<<ans<<endl;
    }

    return 0;
}

马走日

  注意dx和dy，因为马的跳跃方式比较特殊，所以要注意不要写错了

代码

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N=16;

int n,m,x,y;

int dx[8]={2,2,-2,-2,1,1,-1,-1};
int dy[8]={1,-1,1,-1,2,-2,2,-2};

bool vis[N][N];

int ans;

void dfs(int nx,int ny,int cnt)
{
    if(cnt==n*m)
    {
        ans++;
        return;
    }

    for(int i=0;i<8;i++)
    {
        int X=nx+dx[i];
        int Y=ny+dy[i];

        if(X<0 || Y<0 || X>=n || Y>=m || vis[X][Y]) continue;
        vis[X][Y]=true;
        dfs(X,Y,cnt+1);
        vis[X][Y]=false;
    }
}

void solve()
{
    memset(vis,false,sizeof(vis));
    ans=0;

    cin>>n>>m>>x>>y;

    vis[x][y]=true;
    dfs(x,y,1);

    cout<<ans<<endl;

}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin>>t;

    while(t--)
    {
        solve();
    }

    return 0;
}

奇怪的电梯

DFS代码

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N=205;

int K[N];
int dis[N];
int n,A,B;

void dfs(int now,int step)
{
    dis[now]=step;

    int up=now+K[now];
    if(up<=n && step+1<dis[up]) dfs(up,step+1);

    int down=now-K[now];
    if(down>=1 && step+1<dis[down]) dfs(down,step+1);
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>n>>A>>B;

    for(int i=1;i<=n;i++)
    {
        cin>>K[i];
    }

    for(int i=1;i<=n;i++)
    {
        dis[i]=0x3f3f3f3f;
    }

    dfs(A,0);

    if(dis[B]==0x3f3f3f3f)
    {
        cout<<"-1"<<endl;
    }
    else
    {
        cout<<dis[B]<<endl;
    }

    return 0;
}

BFS代码
 

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N=205;

int n,A,B;

int K[N];
bool vis[N];

int ans=-1;

void bfs()
{
    queue<pair<int,int>> q;
    q.push({A,0});
    vis[A]=true;

    while(!q.empty())
    {
        pair<int,int> t=q.front();
        q.pop();

        int now=t.first;
        int step=t.second;

        if(now==B)
        {
            ans=step;
            break;
        }

        int up=now+K[now];

        if(!vis[up] && up<=n)
        {
            vis[up]=true;
            q.push({up,step+1});
        }

        int down=now-K[now];

        if(!vis[down] && down>=1)
        {
            vis[down]=true;
            q.push({down,step+1});
        }

    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>n>>A>>B;

    for(int i=1; i<=n; i++)
    {
        cin>>K[i];
    }

    bfs();

    cout<<ans<<endl;

    return 0;
}

The Lakes

思路

典型的连通块问题，模板题

代码

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N=1005;

int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};

int n,m;

int ans;

int a[N][N];
bool vis[N][N];

int cnt=0;

void dfs(int x,int y)
{
    cnt+=a[x][y];

    for(int i=0;i<4;i++)
    {
        int X=x+dx[i];
        int Y=y+dy[i];

        if(X<1 || Y<1 || X>n || Y>m || vis[X][Y] || a[X][Y]==0) continue;

        vis[X][Y]=true;
        dfs(X,Y);
    }
}

void solve()
{
    cin>>n>>m;

    ans=0;

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            vis[i][j]=false;
        }
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
        }
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(!vis[i][j] && a[i][j]!=0)
            {
                cnt=0;
                vis[i][j]=true;
                dfs(i,j);
                ans=max(ans,cnt);
            }
        }
    }

    cout<<ans<<endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin>>t;

    while(t--)
    {
        solve();
    }

    return 0;
}

Robot Factory

思路

有一定的技巧性，读懂题意很重要，这道题的题意有些难以理解，包含位运算的知识

问题 3744 - YTUOJ 课下可以练习

代码

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N=1005;

int n,m;

int g[N][N];
bool vis[N][N];

int cnt=0;

vector<int> ans;

void dfs(int x,int y)
{
    cnt++;

    if((g[x][y]&8)==0 && x-1>=1 && !vis[x-1][y])
    {
        vis[x-1][y]=true;
        dfs(x-1,y);
    }

    if((g[x][y]&4)==0 && y+1<=m && !vis[x][y+1])
    {
        vis[x][y+1]=true;
        dfs(x,y+1);
    }

    if((g[x][y]&2)==0 && x+1<=n && !vis[x+1][y])
    {
        vis[x+1][y]=true;
        dfs(x+1,y);
    }

    if((g[x][y]&1)==0 && y-1>=1 && !vis[x][y-1])
    {
        vis[x][y-1]=true;
        dfs(x,y-1);
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>n>>m;

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>g[i][j];
        }
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(!vis[i][j])
            {
                vis[i][j]=true;
                cnt=0;
                dfs(i,j);
                ans.push_back(cnt);
            }
        }
    }

    sort(ans.begin(),ans.end(),greater<>());

    for(int i=0;i<ans.size();i++)
    {
        cout<<ans[i]<<" ";
    }


    return 0;
}

King Escape

思路

是八皇后问题的简化版，建议可以先去学习八皇后问题
843. n-皇后问题 - AcWing题库
注意防止数组越界即可

代码

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N=1005;

int n;

bool row[N],col[N],dig[2*N],udig[2*N],vis[N][N];

pair<int,int> a,b,c;

int dx[8]={-1,-1,-1,1,1,1,0,0};
int dy[8]={-1,0,1,-1,0,1,-1,1};

bool f=false;

void dfs(int x,int y)
{
    if(x==c.first && y==c.second)
    {
        f=true;
    }

    for(int i=0;i<8;i++)
    {
        int X=x+dx[i];
        int Y=y+dy[i];

        if(!row[X] && !col[Y] && !dig[X+Y] && !udig[X-Y+n] && !vis[X][Y] && X>=1 && X<=n && Y>=1 && Y<=n)
        {
            vis[X][Y]=true;
            dfs(X,Y);
        }
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>n;

    cin>>a.first>>a.second;
    cin>>b.first>>b.second;
    cin>>c.first>>c.second;

    row[a.first]=true;
    col[a.second]=true;
    dig[a.first+a.second]=true;
    udig[a.first-a.second+n]=true;

    dfs(b.first,b.second);

    if(f==true)
    {
        cout<<"YES"<<endl;
    }
    else
    {
        cout<<"NO"<<endl;
    }


    return 0;
}

Hidden Weights

思路

图的遍历，学会基本的建图，以及图的遍历即可，再加上对于题意的理解，即可

代码 

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N=200010;

bool vis[N];
int dis[N];
vector<pair<int,int>> e[N];

void dfs(int u)
{
    for(auto v:e[u])
    {
        if(!vis[v.first])
        {
            vis[v.first]=true;
            dis[v.first]=dis[u]-v.second;
            dfs(v.first);
        }
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n,m;
    cin>>n>>m;

    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        e[v].push_back({u,w});
        e[u].push_back({v,-w});
    }

    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            vis[i]=true;
            dfs(i);
        }
    }

    for(int i=1;i<=n;i++)
    {
        cout<<dis[i]<<" \n"[i==n];
    }

    return 0;
}

共享单车

思路

YTU 3166 共享单车 DFS 记忆化搜索-CSDN博客

代码 

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N=1005;

int n,m;

char g[N][N];
int dis[N][N];

int ans=0x3f3f3f3f;

void dfs(int x,int y)
{
    if(g[x][y]=='x')
    {
        ans=min(ans,dis[x][y]);
    }

    if(x+1<=n && g[x+1][y]!='*' && dis[x][y]+100 < dis[x+1][y] )//向南
    {
        dis[x+1][y]=dis[x][y]+100;
        dfs(x+1,y);
    }

    if(x-1>=1 && g[x-1][y]!='*' && dis[x][y]+100< dis[x-1][y] )//向北
    {
        dis[x-1][y]=dis[x][y]+100;
        dfs(x-1,y);
    }

    if(y+1<=m && g[x][y+1]!='*' && dis[x][y]+100< dis[x][y+1])//向东
    {
        dis[x][y+1]=dis[x][y]+100;
        dfs(x,y+1);
    }

    if(y-1>=1 && g[x][y-1]!='*' && dis[x][y]+100< dis[x][y-1])//向西
    {
        dis[x][y-1]=dis[x][y]+100;
        dfs(x,y-1);
    }

    if(x+1<=n && y+1<=m && g[x+1][y+1]!='*' && dis[x][y]+141<dis[x+1][y+1])//向东南
    {
        dis[x+1][y+1]=dis[x][y]+141;
        dfs(x+1,y+1);
    }

    if(x+1<=n && y-1>=1 && g[x+1][y-1]!='*' && dis[x][y]+141<dis[x+1][y-1] )//向西南
    {
        dis[x+1][y-1]=dis[x][y]+141;
        dfs(x+1,y-1);
    }

    if(x-1>=1 && y+1<=m && g[x-1][y+1]!='*' && dis[x][y]+141<dis[x-1][y+1] )//向东北
    {
        dis[x-1][y+1]=dis[x][y]+141;
        dfs(x-1,y+1);
    }

    if(x-1>=1  && y-1>=1 && g[x-1][y-1]!='*' && dis[x][y]+141< dis[x-1][y-1])//向西北
    {
        dis[x-1][y-1]=dis[x][y]+141;
        dfs(x-1,y-1);
    }

}

void solve()
{
    cin>>n>>m;

    ans=0x3f3f3f3f;

    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            cin>>g[i][j];
        }
    }

    memset(dis,0x3f,sizeof(dis));

    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            if(g[i][j]=='o')
            {
                dis[i][j]=0;
                dfs(i,j);
            }
        }
    }

    if(ans==0x3f3f3f3f)
    {
        cout<<"-1"<<endl;
    }
    else
    {
        cout<<ans<<endl;
    }

}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin>>t;

    while(t--)
    {
        solve();
    }

    return 0;
}

图的存储

代码

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N=1005;

int g[N][N];
vector<int> adj[N];

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n,m;
    cin>>n>>m;

    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;

        g[u][v]=1;
        g[v][u]=1;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cout<<g[i][j]<<" ";
        }
        cout<<endl;
    }

    for(int i=1;i<=n;i++)
    {
        cout<<adj[i].size()<<" ";

        sort(adj[i].begin(),adj[i].end());

        for(auto x:adj[i])
        {
            cout<<x<<" ";
        }
        cout<<endl;
    }



    return 0;
}

图的遍历

思路

反向建边+dfs，这道题问的是从某个点出发，所能达到的最大的节点，那么不如转化思维，改为，从最大的节点开始进行操作，看看最大的节点可以被哪些节点所到达，那么哪些节点的答案一定是最大节点，从而被标记为不可更新，所以，从n到1进行dfs遍历，就可以得出答案

代码 

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N=100005;

vector<int> e[N];
bool vis[N];
int A[N];

void dfs(int u,int x)
{
    for(auto v:e[u])
    {
        if(!vis[v])
        {
            vis[v]=true;
            A[v]=x;
            dfs(v,x);
        }
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n,m;
    cin>>n>>m;

    for(int i=1;i<=n;i++)
    {
        A[i]=i;
    }

    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;

        e[v].push_back(u);
    }

    for(int i=n;i>=1;i--)
    {
        if(!vis[i])
        {
            vis[i]=true;
            dfs(i,i);
        }
    }

    for(int i=1;i<=n;i++)
    {
        cout<<A[i]<<" \n"[i==n];
    }


    return 0;
}