第一题
输入矩阵行、列、转换方向的次数；
输入矩阵（@表示开始位置，#表示不能通过，.表示可以走）
输入方向序列（EAST、WSET、NORTH、SOUTH）
输出最终位置
（DFS）
#include <iostream>
#include <vector>
using namespace std;
void solve(int posi, int posj, vector<vector<char>> &G, vector<string> &d,
int &endi, int &endj, int n, int m, int k, int cnt) {
if (posi < 1 || posi > n || posj < 1 || posj > m || G[posi][posj] == '#') {
if (cnt == k) {
if (d[cnt] == "EAST") {
endi = posi;
endj = posj - 1;
} else if (d[cnt] == "WEST") {
endi = posi;
endj = posj + 1;
} else if (d[cnt] == "SOUTH") {
endi = posi - 1;
endj = posj;
} else if (d[cnt] == "NORTH") {
endi = posi + 1;
endj = posj;
}
return;
}
if (d[cnt] == "EAST") {
posj--;
} else if (d[cnt] == "WEST") {
posj++;
} else if (d[cnt] == "SOUTH") {
posi--;
} else if (d[cnt] == "NORTH") {
posi++;
}
cnt++;
}
if (d[cnt] == "EAST") {
solve(posi, posj + 1, G, d, endi, endj, n, m, k, cnt);
} else if (d[cnt] == "WEST") {
solve(posi, posj - 1, G, d, endi, endj, n, m, k, cnt);
} else if (d[cnt] == "SOUTH") {
solve(posi + 1, posj, G, d, endi, endj, n, m, k, cnt);
} else if (d[cnt] == "NORTH") {
solve(posi - 1, posj, G, d, endi, endj, n, m, k, cnt);
}
}
int main() {
int n, m, k;
cin >> n >> m >> k;
vector<vector<char>> G(n + 1, vector<char>(m + 1, ' '));
vector<string> d(k + 1, " ");
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> G[i][j];
}
}
for (int i = 1; i <= k; i++) {
cin >> d[i];
}
int endi = 1, endj = 1;
int posi = 1, posj = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (G[i][j] == '@') {
G[i][j] = '.';
posi = i;
posj = j;
}
}
}
solve(posi, posj, G, d, endi, endj, n, m, k, 1);
cout << endi << " " << endj << endl;
} 第二题
给你一个披萨，它由 3n 块不同大小的部分组成，现在你和你的朋友们需要按照如下规则来分披萨：
你挑选 任意 一块披萨。
Alice 将会挑选你所选择的披萨逆时针方向的下一块披萨。
Bob 将会挑选你所选择的披萨顺时针方向的下一块披萨。
重复上述过程直到没有披萨剩下。
每一块披萨的大小按顺时针方向由循环数组 slices 表示。
请你返回你可以获得的披萨大小总和的最大值。
你挑选 任意 一块披萨。
Alice 将会挑选你所选择的披萨逆时针方向的下一块披萨。
Bob 将会挑选你所选择的披萨顺时针方向的下一块披萨。
重复上述过程直到没有披萨剩下。
每一块披萨的大小按顺时针方向由循环数组 slices 表示。
请你返回你可以获得的披萨大小总和的最大值。
（DP）
class Solution {
public:
int calculate(const vector<int>& slices) {
int n = slices.size();
int choose = (n + 1) / 3;
vector<vector<int>> dp(n + 1, vector<int>(choose + 1));
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= choose; ++j) {
dp[i][j] = max(dp[i - 1][j], (i - 2 >= 0 ? dp[i - 2][j - 1] : 0) + slices[i - 1]);
}
}
return dp[n][choose];
}
int maxSizeSlices(vector<int>& slices) {
vector<int> v1(slices.begin() + 1, slices.end());
vector<int> v2(slices.begin(), slices.end() - 1);
int ans1 = calculate(v1);
int ans2 = calculate(v2);
return max(ans1, ans2);
}
};
全部评论
(2) 回帖