#include #include using namespace std; void bfs(vector> &input, vector> &visited, int dir, int score, int pos_n, int pos_m, int N, int M); int ans = 0; 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, visited, 0, 0, 0, 0, N, M); cout << ans << '\n'; return 0; } void bfs(vector> &input, 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; } if (visited[pos_n][pos_m] == 1) { return; } int current_score = score + input[pos_n][pos_m]; if (pos_n == N - 1 && pos_m == M - 1) { ans = max(ans, current_score); return; } visited[pos_n][pos_m] = 1; bfs(input, visited, 0, current_score, pos_n+1, pos_m, N, M); bfs(input, visited, 1, current_score, pos_n-1, pos_m, N, M); bfs(input, visited, 2, current_score, pos_n, pos_m+1, N, M); bfs(input, visited, 3, current_score, pos_n, pos_m-1, N, M); visited[pos_n][pos_m] = 0; return; }