2022-01-17每日刷题打卡

一本通

1255：迷宫问题

【题目描述】

定义一个二维数组：

int maze[5][5] = {

0,1,0,0,0,

0,1,0,1,0,

0,0,0,0,0,

0,1,1,1,0,

0,0,0,1,0, };它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

【输入】

一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。

【输出】

左上角到右下角的最短路径，格式如样例所示。

【输入样例】

0 1 0 0 0

0 1 0 1 0

0 0 0 0 0

0 1 1 1 0

0 0 0 1 0

【输出样例】

(0, 0)

(1, 0)

(2, 0)

(2, 1)

(2, 2)

(2, 3)

(2, 4)

(3, 4)

(4, 4)

先用求迷宫出路的方法，把走出迷宫所需的最短时间ans求出来，准备两个哈希表in和out，以每一步的时间为key，每一步的左边为vul，再求出最短时间的时候，每走一步，就根据当前的时间把位置存入哈希表in中。

然后再从迷宫出口返回入口，从ans一直走到0（求最短时间是每一步++，这里是每一步–）为止，也是把每一步根据时间将坐标存入哈希表中。

总而言之就是把从出口走到入口和入口走到出口的步骤全记录下来，然后根据in哈希表，从时间1遍历到时间ans，判断相同时间下，两个哈希表有没有相同的元素，如果有，那个相同元素就是正确的走法，输出它，然后再用下一个时间继续找相同元素即可。

#include<iostream>
using namespace std;
#include<vector>
#include<string.h>
#include<algorithm>
#include<unordered_map>

typedef pair<int, int>PII;
const int N = 10;
int g[N][N],h[N][N],q[N][N];
PII que[N * N];
unordered_map<int, vector<PII>>myin, myout;

int bfs()
{
    int dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 };
    int hh = 0, tt = 0;
    memset(h, -1, sizeof h);
    memset(q, -1, sizeof q);   
    que[0] = { 0,0 };
    h[0][0] = 1;
    
    while (hh <= tt)
    {
        auto t = que[hh++];
        myin[h[t.first][t.second]].push_back(t);
        for (int i = 0; i < 4; i++)
        {
            int x = t.first + dx[i], y = t.second + dy[i];
            if (x >= 0 && x < 5 && y >= 0 && y < 5 && g[x][y] == 0 && h[x][y] == -1)
            {
                h[x][y] = h[t.first][t.second] + 1;
                que[++tt] = { x,y };
            }
        }
    }
    int ans = h[4][4];
    hh = 0, tt = 0;
    q[4][4] = ans;
    que[0] = { 4,4 };
    while (hh <= tt)
    {
        auto t = que[hh++];
        myout[q[t.first][t.second]].push_back(t);
        for (int i = 0; i < 4; i++)
        {
            int x = t.first + dx[i], y = t.second + dy[i];
            if (x >= 0 && x < 5 && y >= 0 && y < 5 && g[x][y] == 0 && q[x][y] == -1)
            {
                q[x][y] = q[t.first][t.second] - 1;
                que[++tt] = { x,y };
            }
        }
    }
    return ans;
}

PII serch(PII a, vector<PII>& b)
{
    int n = b.size();
    for (int i = 0; i < n; i++)
    {
        if (b[i].first == a.first && b[i].second == a.second)
        {
            return a;
        }
    }
    return { -1,-1 };
}

int main()
{
    memset(g, -1, sizeof g);
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++)
            cin >> g[i][j];
    int ans=bfs();
    for (int i = 1; i <= ans; i++)
    {
        for (int j = 0; j < myin[i].size(); j++)
        {
            auto t = serch(myin[i][j], myout[i]);
            if (t.first != -1 && t.second != -1)
            {
                cout << "(" << t.first << ", " << t.second << ")" << endl;
                break;
            }
        }
    }

    return 0;
}

1330：【例8.3】最少步数

【题目描述】

在各种棋中，棋子的走法总是一定的，如中国象棋中马走“日”。有一位小学生就想如果马能有两种走法将增加其趣味性，因此，他规定马既能按“日”走，也能如象一样走“田”字。他的同桌平时喜欢下围棋，知道这件事后觉得很有趣，就想试一试，在一个（100×100）的围棋盘上任选两点A、B，A点放上黑子，B点放上白子，代表两匹马。棋子可以按“日”字走，也可以按“田”字走，俩人一个走黑马，一个走白马。谁用最少的步数走到左上角坐标为(1,1)的点时，谁获胜。现在他请你帮忙，给你A、B两点的坐标，想知道两个位置到（1,1）点可能的最少步数。

【输入】

A、B两点的坐标。

【输出】

最少步数。

【输入样例】
12 16 
18 10

【输出样例】
8 
9

还是广搜，和走迷宫问题类似，只不过走迷宫只有上下左右四个方向，这里按照日字和田字一共可以有12个方向，就用这12个方向换掉走迷宫的四个方向即可。为了省时间，我们可以找到题目所给位置时就立刻return，而不是按照走迷宫那样把所有步数都走完了才返回。

#include<iostream>
using namespace std;
#include<vector>
#include<string.h>
#include<algorithm>
#include<unordered_map>

typedef pair<int, int>PII;
const int N = 110;
int g[N][N],h[N][N];
PII que[N * N];

int d[12][2] = { {1,2},{-1,2},{1,-2},{2,1},{-2,1},{2,-1},{-1,-2},{2,2},{2,-2},{-2,2},{-2,-2} };

int bfs(int a, int b)
{
    int hh = 0, tt = 0;
    memset(h, -1, sizeof h);
    que[0] = { 1,1 };
    h[1][1] = 0;
    while (hh <= tt)
    {
        auto t = que[hh++];
        for (int i = 0; i < 12; i++)
        {
            int x = t.first + d[i][0], y = t.second + d[i][1];
            if (x >= 1 && x <= 100 && y >= 1 && y <= 100 && h[x][y] == -1)
            {
                h[x][y] = h[t.first][t.second] + 1;
                if (x == a && y == b)return h[x][y];
                que[++tt] = { x,y };
            }
        }
    }
    return {};
}

int main()
{

    memset(g, -1, sizeof g);
    for (int i = 0; i < 2; i++)
    {
        int a, b;
        cin >> a >> b;
        cout << bfs(a, b) << endl;
    }
    

    return 0;
}

蓝桥杯——算法提高

算法提高 区间覆盖问题

问题描述

给出一段长度为n的区间和m条线段，每条线段有其起始点xi和终止点yi，现在我们想知道最少用几条线段就可以覆盖这一个区间。

输入格式

第一行包含两个整数n，m

接下来m行 每行两个数 xi yi 保证 xi<=yi

输出格式

输出1行，包含一个整数，表示最少线段数。如果无法覆盖 输出-1；

样例输入

5 3

1 3

3 4

4 5

样例输出

3

数据规模和约定

n<=10^6

m<=10^5

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
struct Range
{
    int l, r;
    bool operator< (const Range &W)const
    {
        return l < W.l;
    }
}range[N];

int main()
{
    int st=1, ed;
    scanf("%d", &ed);
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        range[i] = {l, r};
    }

    sort(range, range + n);

    int res = 0;
    bool success = false;
    for (int i = 0; i < n; i ++ )
    {
        int j = i, r = -2e9;
        while (j < n && range[j].l <= st)
        {
            r = max(r, range[j].r);
            j ++ ;
        }

        if (r < st)
        {
            res = -1;
            break;
        }

        res ++ ;
        if (r >= ed)
        {
            success = true;
            break;
        }

        st = r;
        i = j - 1; 
    }

    if (!success) res = -1;
    printf("%d\n", res);

    return 0;
}