目录

1.ISBN号码

2.kotori和迷宫

3.矩阵最长递增路径

---

1.ISBN号码

链接https://www.nowcoder.com/practice/95712f695f27434b9703394c98b78ee5?tpId=290&tqId=39864&ru=/exam/oj

提取题意，模拟一下即可。

#include <iostream>
using namespace std;
int main() {string s;cin >> s;int n = s.size();int sum = 0;int k = 1;for (int i = 0; i < n - 1; ++i){if (s[i] != '-'){sum += (s[i] - '0') * k;++k;}}sum %= 11;if (sum == 10 && s[n - 1] == 'X' || sum == (s[n - 1] - '0'))cout << "Right" << endl;else{for (int i = 0; i < n - 1; ++i)cout << s[i];if (sum == 10)cout << 'X';elsecout << sum;}return 0;
}

2.kotori和迷宫

链接https://ac.nowcoder.com/acm/problem/50041

BFS / DFS（宽度 / 深度 优先遍历即可）

DFS：（我写的DFS目前还是没找到为什么有测试用例过不去）

// DFS(有测试用例过不了)
#include <iostream>
using namespace std;
const int N = 35;int n, m;
int cnt = 0;
int sum = 0x3f3f3f3f;
char arr[N][N];
bool vis[N][N] = { false };
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };void DFS(int d, int x, int y)
{if (arr[x][y] == 'e'){cnt++;sum = min(sum, d);return;}vis[x][y] = true;for (int i = 0; i < 4; ++i){int a = x + dx[i];int b = y + dy[i];if (a >= 1 && a <= n && b >= 1 && b <= m && !vis[a][b] && arr[a][b] != '*'){DFS(d + 1, a, b);}}vis[x][y] = false;
}int main()
{int x, y;cin >> n >> m;for (int i = 1; i <= n; ++i){for (int j = 1; j <= m; ++j){cin >> arr[i][j];if (arr[i][j] == 'k'){x = i;y = j;}}}DFS(0, x, y);if (cnt == 0)cout << -1;elsecout << cnt << ' ' << sum << endl;return 0;
}

 BFS：（因为可以保证第一次找到的一定是最近的）

// BFS
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 35;
int x1, y1; // 标记起点位置
int n, m;
char arr[N][N];
int dist[N][N];
queue<pair<int, int>> q;
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
void bfs()
{memset(dist, -1, sizeof dist);dist[x1][y1] = 0;q.push({ x1, y1 });while (q.size()){auto [x2, y2] = q.front();q.pop();for (int i = 0; i < 4; i++){int a = x2 + dx[i], b = y2 + dy[i];if (a >= 1 && a <= n && b >= 1 && b <= m && dist[a][b] == -1 &&arr[a][b] != '*'){dist[a][b] = dist[x2][y2] + 1;if (arr[a][b] != 'e'){q.push({ a, b });}}}}
}
int main()
{cin >> n >> m;for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){cin >> arr[i][j];if (arr[i][j] == 'k'){x1 = i, y1 = j;}}}bfs();int count = 0, ret = 1e9;for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){if (arr[i][j] == 'e' && dist[i][j] != -1){count++;ret = min(ret, dist[i][j]);}}}if (count == 0) cout << -1 << endl;else cout << count << " " << ret << endl;return 0;
}

3.矩阵最长递增路径

链接https://www.nowcoder.com/practice/7a71a88cdf294ce6bdf54c899be967a2?tpId=196&tqId=37184&ru=/exam/oj

深度优先遍历即可（DFS）：

#include <cstdlib>
#include <vector>
class Solution {
public:const static int N = 1010;bool vis[N][N] = { false };int dx[4] = { 0, 0, 1, -1 };int dy[4] = { 1, -1, 0, 0 };int n, m, ret = 0;vector<vector<int>> arr;bool Check(int x, int y){for (int i = 0; i < 4; ++i){int a = x + dx[i];int b = y + dy[i];if (a >= 0 && a < n && b >= 0 && b < m && arr[x][y] < arr[a][b])return true;}return false;}void DFS(int x, int y, int d){if (!Check(x, y)){ret = max(ret, d);return;}vis[x][y] = true;for (int i = 0; i < 4; ++i){int a = x + dx[i];int b = y + dy[i];if (a >= 0 && a < n && b >= 0 && b < m && !vis[a][b] && arr[x][y] < arr[a][b]){DFS(a, b, d + 1);}}vis[x][y] = false;}int solve(vector<vector<int>>& matrix) {arr = matrix;n = matrix.size();m = matrix[0].size();for (int i = 0; i < n; ++i)for (int j = 0; j < m; ++j)DFS(i, j, 0);return ret + 1;}
};