【今日三题】ISBN号码(模拟) / kotori和迷宫(BFS最短路) / 矩阵最长递增路径(dfs)

ISBN号码(模拟)

• ISBN号码

#include <iostream>
#include <string>
using namespace std;

string s;
int sum, cnt = 1, n;

int main()
{
    cin >> s;
    n = s.size();
    for (int i = 0; i < n - 1; i++)
    {
        if (s[i] != '-')
        {
            sum += (s[i] - '0') * cnt;
            cnt++;
        }
    }
    sum %= 11;
    if (sum == (s[n - 1] - '0') || (sum == 10 && s[n - 1] == 'X'))
    {
        cout << "Right" << endl;
    }
    else {
        s[n - 1] = (sum == 10 ? 'X' : (sum + '0'));
        cout << s << endl;
    }
    return 0;
}

kotori和迷宫(BFS最短路)

• kotori和迷宫

#include <iostream>
#include <queue>
using namespace std;

int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
const int N = 31;
bool used[N][N];
char arr[N][N];
using pii = pair<int, int>;
queue<pii> q;
int n, m, cnt, dist, step;

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> arr[i][j];
            if (arr[i][j] == 'k')
            {
                q.push({i, j});
                used[i][j] = true;
            }
        }
    }
    while (q.size())
    {
        step++;
        int sz = q.size();
        while (sz--)
        {
            auto [a, b] = q.front();
            q.pop();
            for (int i = 0; i < 4; i++)
            {
                int x = a + dx[i], y = b + dy[i];
                if (x >= 0 && x < n && y >= 0 && y < m && !used[x][y] && arr[x][y] != '*')
                {
                    if (arr[x][y] == 'e')
                    {
                        if (cnt == 0) dist = step;
                        cnt++;
                    }
                    else if (arr[x][y] == '.')
                    {
                        q.push({x, y});
                    }
                    used[x][y] = true;
                }
            }
        }
    }
    if (cnt > 0) cout << cnt << " " << dist << endl;
    else cout << -1 << endl;
    return 0;
}

矩阵最长递增路径(dfs)

• 矩阵最长递增路径

class Solution {
    int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
    bool used[1001][1001] = {};
    int n, m;
public:
    int solve(vector<vector<int> >& matrix) {
        n = matrix.size(), m = matrix[0].size();
        int len = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                len = max(len, dfs(matrix, i, j));
            }
        }
        return len;
    }
    int dfs(const vector<vector<int>> &matrix, int i, int j)
    {
        int len = 1;
        for (int k = 0; k < 4; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if (x >= 0 && x < n && y >= 0 && y < m && !used[x][y] && matrix[x][y] > matrix[i][j])
            {
                used[x][y] = true;
                len = max(len, dfs(matrix, x, y) + 1);
                used[x][y] = false;
            }
        }
        return len;
    }
};

本篇文章的分享就到这里了，如果您觉得在本文有所收获，还请留下您的三连支持哦~