#include #include using namespace std; void bfs(vector> &input, vector>> &best, vector> &visited, int dir, int score, int pos_n, int pos_m, int N, int M); int main() { int N, M; cin >> N >> M; vector> input(N, vector(M, 0)); vector>> best(N, vector>(M, vector(4, 0))); vector> visited(N, vector(M, 0)); for (int i = 0; i < N; ++i) { for (int j = 0; j < M; ++j) { cin >> input[i][j]; } } bfs(input, best, visited, 0, 0, 0, 0, N, M); int min1 = max(best[N-1][M-1][0], best[N-1][M-1][1]); int min2 = max(best[N-1][M-1][2], best[N-1][M-1][3]); cout << max(min1, min2) << '\n'; return 0; } void bfs(vector> &input, vector>> &best, vector> &visited, int dir, int score, int pos_n, int pos_m, int N, int M) { if (pos_n < 0 || pos_n >= N || pos_m < 0 || pos_m >= M) { return; } int current_score = score + input[pos_n][pos_m]; if (current_score <= best[pos_n][pos_m][dir]) { return; } if (visited[pos_n][pos_m] == 1) { return; } best[pos_n][pos_m][dir] = current_score; visited[pos_n][pos_m] = 1; bfs(input, best, visited, 0, current_score, pos_n+1, pos_m, N, M); bfs(input, best, visited, 1, current_score, pos_n-1, pos_m, N, M); bfs(input, best, visited, 2, current_score, pos_n, pos_m+1, N, M); bfs(input, best, visited, 3, current_score, pos_n, pos_m-1, N, M); visited[pos_n][pos_m] = 0; return; }