首页 > 其他分享 >week4题解

week4题解

时间:2022-11-18 13:00:57浏览次数:45  
标签:10 sy sx int 题解 map1 && week4

1.深度优先搜索

 

 

 思路:以固定的移动顺序走迷宫,若能到终点则记一次

到终点后回溯到前一个有分岔的地方,走另一条路线

若走到死路也同样回溯到前一个有分叉的地方。

最终遍历所有路线

#include <bits/stdc++.h>
using namespace std;
int n,m,t,sx,sy,fx,fy,answer=0;
int map1[10][10];
bool pass[10][10];
//计算顺序为 右、下、左、上
int ax[4]={1,0,-1,0};
int ay[4]={0,-1,0,1};
void dfs(int x,int y)
{
    if(x==fx&&y==fy)
    {
        answer+=1;
        return;
    }
    for(int i=0;i<4;i++)
    {
        //移动后的x,y 
        int xchange=x+ax[i];
        int ychange=y+ay[i];
        //同时满足:不超边界、不是障碍、不曾经过 
        if(xchange>0&&ychange>0&&xchange<=m&&ychange<=n&&map1[xchange][ychange]!=1&&pass[xchange][ychange]==0)
        {
            pass[xchange][ychange]=1;//点[xchange][ychange]已经经过 
            dfs(xchange,ychange);//下一步
            pass[xchange][ychange]=0;//这一步之后的所有路径都被试过,往前回溯 
        }
    }
}

所写函数dfs包括了移动一步,进行下一步和退回前一步三个操作

pass所记录的已经经过的位置是随路径的变化而变化的

接下来只要使用函数即可

int main()
{
    cin>>n>>m>>t>>sx>>sy>>fx>>fy;
    //map中1为障碍 
    for(int i=0;i<t;i++)
    {
        int a,b;
        cin>>a>>b;
        map1[a][b]=1;
    }
    //经过起点
    pass[sx][sy]=1;
    dfs(sx,sy);
    cout<<answer;
    
    return 0;
}

2.广度优先搜索

 

思路:因为要考虑重复经过的问题,我们要求出经过某个点的最快路径就不能一条路走到底

因此要一步步走,将第一步能到的位置储存,再从第一步开始将第二步的所有位置储存

因为无法判定一共有多少步所以只能一步步走,因为无法移动到已经移动到的地方,所以最终会停止循环

根据这个特性可以开一个队列,先计算完步数小的后计算步数大的

#include <bits/stdc++.h>
using namespace std;
int n,m,x,y;
int map1[450][450];
//8种走法 
int ax[8]={-2,-1,1,2,2,1,-1,-2};
int ay[8]={1,2,2,1,-1,-2,-2,-1};
queue <pair<int,int> >q; 
void bfs()
{
    while(q.empty()==false)//没有起始点后结束 
    {
        int x=q.front().first;
        int y=q.front().second;
        q.pop();//取出最前一组坐标为x,y并在队列中删除 
        for(int i=0;i<8;i++)
        {
            //移动后的x,y 
            int xchange=x+ax[i];
            int ychange=y+ay[i];
            //同时满足:不超边界,不过重复点 
            if(xchange>0&&ychange>0&&xchange<=n&&ychange<=m&&map1[xchange][ychange]==-1)
            {
                q.push(make_pair(xchange,ychange));//重置起始点 
                map1[xchange][ychange]=map1[x][y]+1;//点[xchange][ychange]已经经过
            }
        }
    }   
}

其中的bfs函数包括:取出要运算的坐标,移动,新增起始点 三个操作

只要是-1就表明还未经过,由此判断是否可以经过

最终处理后的map1就是要输出的结果

int main()
{
    cin>>n>>m>>x>>y;
    //map初始化
    for(int i=0;i<402;i++)
    {
        for(int j=0;j<402;j++)
        {
            map1[i][j]=-1;
        }
    }
    //经过起点
    map1[x][y]=0;
  //将起点存入队列 q.push(make_pair(x,y)); bfs(); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { printf("%-5d",map1[i][j]);//注意输出格式 } cout<<endl; } return 0; }

标签:10,sy,sx,int,题解,map1,&&,week4
From: https://www.cnblogs.com/if-I-can-fly/p/16902849.html

相关文章

  • DTOJ-2022-11-10-测试-题解
    题目链接ABCA这个套路已经出现了很多次了就是两条线之间的网格图路径数,做法呢就是容斥题意求满足以下条件的\(n\timesm\)的矩阵的个数对\(10^9+7\)取模对于......
  • vue 项目源码映射失败问题解决
    目录vue项目源码映射失败问题解决前言解决方案效果参考vue项目源码映射失败问题解决前言不知何时起,项目控制台调试进入源代码变成编译后的文件了,调试起来十分不便,强迫......
  • 服务商系统集中高频交易CPU飙升问题解决优化过程
    通过创建数据表索引,有效提升系统性能。一、问题背景在11月10日下午5点,出现channel异步下发消息队列消息积压报警,经排查分析是因为channel请求鑫某亿服务商落单时间过长......
  • Ubuntu常见问题解决
    Ubuntu常见问题解决1.ubuntu系统上安装qt5.12后无法调试运行 原因:缺少gcc、g++、make、libgl1sudoapt-getinstallgccsudoapt-getinstallg++sudoapt-getinstallmak......
  • 2022.11.17模拟赛题解
    从今天起更换码风。猜数字两种做法:二分,哈希二分记函数\(g(x)\)表示数字\(x\)在\(10\)进制下的位数。可以观察到对于正整数\(k(k\ge2)\),都有\(g(k^k)<g((k+1)......
  • LG4778 Counting swaps 题解
    LG4778Countingswaps给定你一个\(1\simn\)的排列\(p\),可进行若干次操作,每次选择两个整数\(x,y\),交换\(p_x,p_y\)。用最少的操作次数将给定排列变成单调上升的序......
  • 今晚题解
    题意概述给定一张\(n\)个点\(m\)条边的有向图\(G\)。有\(n\)个硬币。初始时有的正面朝上,有的反面朝上。每次你可以手动翻转一枚。如果在\(G\)中有边\(a\righ......
  • Aizu 2378 SolveMe 题解 (置换,计数)
    题目链接题意简述有一个n个点的有向图,每个点有两条出边,称为A边和B边。称一种构图是好的,当且仅当对于所有i,从第i个点出发,先连走x次A边,走1次B边,再连走y次A边,走1次B边,再走z......
  • CF1181C Flag 题解
    题意:问在一个\(n\timesm\)的平面里有多少旗帜,旗帜的定义是三条宽度相等的带子,相邻的带子颜色不能相同(第一和第三条的颜色可以相同)。考虑以左上角统计旗帜,预处理每个点......
  • 小程序获取不到用户头像和昵称返回微信用户问题解决,即小程序授权获取用户头像规则调整
    最近好多同学在学习石头哥小程序课程的时候,遇到了下面这样的问题,在小程序授权获取用户头像和昵称时,获取到的是下面这样的。到底是什么原因导致的呢,去小程序官方文档一看,又是......