#include #include using namespace std; void bfs(vector> &input, vector> &best, 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, 0)); for (int i = 0; i < N; ++i) { for (int j = 0; j < M; ++j) { cin >> input[i][j]; } } bfs(input, best, 0, 0, 0, N, M); cout << best[N-1][M-1] << '\n'; return 0; } void bfs(vector> &input, vector> &best, 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 (0 != best[pos_n][pos_m]) { return; } best[pos_n][pos_m] = current_score; bfs(input, best, current_score, pos_n+1, pos_m, N, M); bfs(input, best, current_score, pos_n-1, pos_m, N, M); bfs(input, best, current_score, pos_n, pos_m+1, N, M); bfs(input, best, current_score, pos_n, pos_m-1, N, M); return; }