每日一作业

大家好，我是小白白泽，今天是我开始打卡学习的第一天，以下内容也仅代表我的方法，如果你有别的更好，更优的方法，可以和我一起讨论。

一、迷宫

题目背景
给定一个N*M方格的迷宫，迷宫里有T处障碍，障碍处不可通过。给定起点坐标和终点坐标，问: 每个方格最多经过1次，有多少种从起点坐标到终点坐标的方案。在迷宫中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。

题目描述
无

输入格式
第一行N、M和T，N为行，M为列，T为障碍总数。第二行起点坐标SX,SY，终点坐标FX,FY。接下来T行，每行为障碍点的坐标。

输出格式
给定起点坐标和终点坐标，问每个方格最多经过1次，从起点坐标到终点坐标的方案总数。

原题链接:迷宫 - 洛谷

解题思路：从题目中可以看出，这题应该使用搜索思想，而常用的搜索方法包括dfs(深度优先遍历)和bfs，本题我用的是dfs，应该也可以使用bfs(但是我懒)。

#include<iostream>
using namespace std;
int map[6][6];
int v[6][6];
int x1[4]={-1,1,0,0};
int y1[4]={0,0,-1,1};
int n,m,t,sx,sy,ex,ey,cnt;//n,m代表布局大小，sx，sy，代表着起点下标，ex，ey，代表终点下标
void dfs(int x,int y)
{
    if(x==ex&&y==ey)//结束条件，当我们移动到（ex,ey）这个点时就记录一次方案。
    {
        cnt ;return ;
    }
    else
    for(int i=0;i<4;i )
    {
        if(v[x x1[i]][y y1[i]]==0&&map[x x1[i]][y y1[i]]==1)
        {
            v[x][y]=1;//当前这个点已经被走过了，标记
            dfs(x x1[i],y y1[i]);
            v[x][y]=0;//重置状态，方便下一次的遍历
        }
    }
    return ;
}
int main()
{
    cin>>n>>m>>t;
    cin>>sx>>sy>>ex>>ey;
    for(int i=1;i<=n;i )
        for(int j=1;j<=m;j )
            map[i][j]=1;//存储当前的迷宫布局。
    while(t--)
    {
        int x,y;cin>>x>>y;
        map[x][y]=2;//表示障碍物 
    }
    dfs(sx,sy);
    cout<<cnt;
    return 0;
}
二、 数字反转（升级版）
建议大家在做这道题前可以先把数字反转给做了，这样思路应该清晰一点。
题目描述
给定一个数，请将该数各个位上数字反转得到一个新数。

这次与NOIp2011普及组第一题不同的是：这个数可以是小数，分数，百分数，整数。

整数反转是将所有数位对调。

小数反转是把整数部分的数反转，再将小数部分的数反转，不交换整数部分与小数部分。

分数反转是把分母的数反转，再把分子的数反转，不交换分子与分母。

百分数的分子一定是整数，百分数只改变数字部分。

输入格式
一个数 ss

输出格式
一个数，即 ss 的反转数

输入输出样例
输入 #1复制    输出 #1复制
5087462        2647805
输入 #2复制    输出 #2复制
600.084        6.48
输入 #3复制    输出 #3复制
700/27        7/72
输入 #4复制    输出 #4
8670%        768%
本题思路：哼哼，这题还是有点难度的，作为被这种类型的题目坑过几次的人来说，我认为这个要注意以下几点：
（1）整数需要注意反转后的结果不能以0开头，因为我们生活中没有从0100这种类型的十进制数啊，但要注意，0反转了之后还是0啊！！！
（2）小数和整数其实是一样的，只不过“.”之前的数是一部分 可以是0开头，比如0.10=>0.01，“.”之后的数是一部分 小数点后面的0要省略。
（3）分数与小数有些地方是一样的，分子可以是0
（4）百分号%的前面的数字就是整数，可以看作整数规则，在输出的时候加上%
AC代码：
#include<iostream>
#include<string>
using namespace std;
long long a,b;
char ch='\0';
string s;
int main()
{
    cin>>s;
    long long jc=1,flag=0;
    for(int i=0;i<s.size();i )
    {
        if(s[i]<'0'||s[i]>'9')//如果遇到了不是整数的，那就代表当前字符是分隔符/,%,"."
        {
            flag=1; jc=1;//jc代表进位，这里重置是为了分隔符后面的数字进位。
            ch=s[i];
            continue;
        } 
        if(flag==0)//第一种情况，还未遇到分隔符的整数，用变量a来存储
        {
            a =(s[i]-48)*jc;
            jc*=10;
            continue;
        }
        if(flag==1)//第二种情况，现在我们遇到分隔符了，用变量b来存储当前整数
        {
            if(b==0) //为什么这里特判b==0呢？因为当分隔符后面的数字以0开头的话，我们的数字是不能进位的，如123.012=>321.21，如果进位了的话就会变成123.012=>321.210
            {
                b =s[i]-48;
                continue;
            }
            jc*=10;
            b =jc*(s[i]-48);
            continue;
        }
    }
    //输出的时候跟上分隔符
    if(ch=='\0') cout<<a;
    else if(ch=='/'||ch=='.') cout<<a<<ch<<b;
    else if(ch=='%') cout<<a<<ch;
    return 0;
}
三、查找文献
题目链接：https://www.luogu.com.cn/problem/P5318
题目描述
小K 喜欢翻看洛谷博客获取知识。每篇文章可能会有若干个（也有可能没有）参考文献的链接指向别的博客文章。小K 求知欲旺盛，如果他看了某篇文章，那么他一定会去看这篇文章的参考文献（如果他之前已经看过这篇参考文献的话就不用再看它了）。

假设洛谷博客里面一共有 n(n\le10^5)n(n≤10 5 ) 篇文章（编号为 1 到 nn）以及 m(m\le10^6)m(m≤10 6 ) 条参考文献引用关系。目前小 K 已经打开了编号为 1 的一篇文章，请帮助小 K 设计一种方法，使小 K 可以不重复、不遗漏的看完所有他能看到的文章。

这边是已经整理好的参考文献关系图，其中，文献 X → Y 表示文章 X 有参考文献 Y。不保证编号为 1 的文章没有被其他文章引用。

请对这个图分别进行 DFS 和 BFS，并输出遍历结果。如果有很多篇文章可以参阅，请先看编号较小的那篇(因此你可能需要先排序)。

题目思路：使用邻接表来存储树的结构，然后使用DFS和BFS遍历，题目要求从编号较小的篇幅始，所以记得排序。

 AC代码：
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
int n,m,cnt;
vector<int>ver[100005];
bool vis[100005];
void dfs(int x)
{
    vis[x]=1;//标记
    cout<<x<<" ";
    cnt ;
    if(cnt==n)
    return ;
    for(int i=0;i<ver[x].size();i )
    {
        if(vis[ver[x][i]]==0)//遍历下一个未被访问过的结点
        dfs(ver[x][i]);
    }
}
queue<int>q;
void bfs(int x)
{
    vis[x]=1;
    q.push(x);
    while(!q.empty())
    {
        int t=q.front();
        cout<<t<<" ";
        q.pop();
        for(int i=0;i<ver[t].size();i )
        {
            if(vis[ver[t][i]]==0)
            {
                q.push(ver[t][i]);
                vis[ver[t][i]]=1;
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    while(m--)
    {
        int u,v;cin>>u>>v;
        ver[u].push_back(v);
    }
    for(int i=1;i<=n;i )
    {
        if(!ver[i].empty())
        sort(ver[i].begin(),ver[i].end());
    }
    dfs(1);
    cout<<endl;
    memset(vis,0,n 1);
    bfs(1);
    return 0;
} 

谢谢你能看到这里，虽然我的代码不一定是最优的，但希望能给你一定小小的帮助。

这篇好文章是转载于：学新通技术网