#include #include using namespace std; vector get_neighbours(int node, int N, int M) { int row_nm = node / M; vector neighbours; if(node % M) neighbours.push_back(node - 1); if ((node % M) + 1 < M) neighbours.push_back(node + 1); if (row_nm) neighbours.push_back(node - M); if (row_nm + 1 < N) neighbours.push_back(node + M); for(int neigh : neighbours) { if(neigh < 0) exit(42); if(neigh >= N*M) exit(43); } return neighbours; } //returns score int dfs(int node, vector visited, int cum_sum, vector &costs, int &N, int&M, vector path, int &best_solution_ever) { path.push_back(node); cum_sum += costs[node]; if(!visited[node]) { visited[node] = true; } else { return 0; } if(node + 1 == N*M) { //we reach the end best_solution_ever = max(cum_sum, best_solution_ever); // cout << "End of path with cum_sum " << cum_sum << endl; // for (int n : path) { // cout << n << " "; // } // cout << endl; return cum_sum; } int max_of_neighbours = 0; int heuristic = (N*M - path.size()) * 1000; if(cum_sum + heuristic < best_solution_ever) return 0; for(int neighbour : get_neighbours(node, N, M)) { max_of_neighbours = max(max_of_neighbours, dfs(neighbour, visited, cum_sum, costs, N, M, path, best_solution_ever)); } return max_of_neighbours; } int main() { int N, M; cin >> N >> M; int n_nodes = N*M; vector costs(n_nodes, -1); for(int node_idx = 0; node_idx < n_nodes; node_idx++) { cin >> costs[node_idx]; } vector visited(n_nodes, false); vector paths(0); int best_solution_ever = 0; int max_score = dfs(0, visited, 0, costs, N, M, paths, best_solution_ever); cout << max_score; return 0; }