#include <iostream>
#include <vector>
#include <algorithm>
// 矩阵，就一二维数组
using matrix_t = std::vector<std::vector<ssize_t>>;
// 一个标记，递归的时候需要知道哪些元素已经访问过了
using matrix_mark_t = std::vector<std::vector<bool>>;
// 矩阵中的点，这里只保存点的y值和x值
using point_t = std::pair<size_t, size_t>;
// 一个路径，就是一堆有顺序的点
using path_t = std::vector<point_t>;
bool operator==(const point_t &lhs, const point_t &rhs) {
return lhs.first == rhs.first && lhs.second == rhs.second;
}
// 判断给定点是否有效，是否可以用给定点访问矩阵
bool point_valid(const matrix_t &data, const point_t &point) {
if(data.size() <= point.first) return false;
if(data[0].size() <= point.second) return false;
return true;
}
// 获取指定路径上的值
ssize_t get_path_value(const matrix_t &data, const path_t *path) {
ssize_t result = 0;
for(const auto &i: *path) {
result += data[i.first][i.second];
}
return result;
}
// 在4条路径上面选一个最大的
const path_t *select_path(const matrix_t &data, const path_t *top_path, const path_t *bottom_path, const path_t *left_path, const path_t *right_path) {
ssize_t top_value = get_path_value(data, top_path);
ssize_t bottom_value = get_path_value(data, bottom_path);
ssize_t left_value = get_path_value(data, left_path);
ssize_t right_value = get_path_value(data, right_path);
std::vector<std::pair<const path_t *, ssize_t>> temp;
if(top_path->size()) temp.push_back(std::pair<const path_t *, ssize_t>{top_path, top_value});
if(bottom_path->size()) temp.push_back(std::pair<const path_t *, ssize_t>{bottom_path, bottom_value});
if(left_path->size()) temp.push_back(std::pair<const path_t *, ssize_t>{left_path, left_value});
if(right_path->size()) temp.push_back(std::pair<const path_t *, ssize_t>{right_path, right_value});
if(!temp.size()) return NULL;
std::sort(temp.begin(), temp.end(), [](const auto &a, const auto &b) -> bool {return a.second > b.second;});
return temp[0].first;
}
// 返回从开始点到结束点之间的所有路径中值最大的那条路径
const path_t get_max_path(const matrix_t &data, matrix_mark_t &matrix_mark, const point_t &begin_point, const point_t &end_point) {
path_t result; result.push_back(begin_point);
if(begin_point == end_point) return result;
matrix_mark[begin_point.first][begin_point.second] = true;
path_t top_path;
point_t top_point = point_t{begin_point.first - 1, begin_point.second};
if(point_valid(data, top_point) && !matrix_mark[top_point.first][top_point.second]) {
top_path = get_max_path(data, matrix_mark, top_point, end_point);
}
path_t bottom_path;
point_t bottom_point = point_t{begin_point.first + 1, begin_point.second};
if(point_valid(data, bottom_point) && !matrix_mark[bottom_point.first][bottom_point.second]) {
bottom_path = get_max_path(data, matrix_mark, bottom_point, end_point);
}
path_t left_path;
point_t left_point = point_t{begin_point.first, begin_point.second - 1};
if(point_valid(data, left_point) && !matrix_mark[left_point.first][left_point.second]) {
left_path = get_max_path(data, matrix_mark, left_point, end_point);
}
path_t right_path;
point_t right_point = point_t{begin_point.first, begin_point.second + 1};
if(point_valid(data, right_point) && !matrix_mark[right_point.first][right_point.second]) {
right_path = get_max_path(data, matrix_mark, right_point, end_point);
}
matrix_mark[begin_point.first][begin_point.second] = false;
const path_t *path = select_path(data, &top_path, &bottom_path, &left_path, &right_path);
if(path) result.insert(result.end(), path->begin(), path->end());
return result;
}
std::ostream &operator<<(std::ostream &os, const path_t &rhs) {
bool flag = false;
for(const auto &i: rhs) {
if(flag) os << std::endl;
os << "(" << i.second << "," << i.first << ")";
flag = true;
}
return os;
}
int main() {
matrix_t data;
size_t n, x, y; std::cin >> n >> x >> y;
--x; --y;
for(size_t y = 0; y < n; ++y) {
data.push_back(std::vector<ssize_t>());
for(size_t x = 0; x < n; ++x) {
ssize_t temp; std::cin >> temp;
data[y].push_back(temp);
}
}
matrix_mark_t matrix_mark(n, std::vector<bool>(n, false));
path_t path = get_max_path(data, matrix_mark, point_t{y, x}, point_t{0, 0});
std::cout << path << std::endl;
return 0;
}
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
楼主
显身卡
发表于 2021-12-5 20:08:36