#include #include #include using namespace std; int** matrix; int** visited; int N, M, result, sum; int dx[4] = {1, -1, 0, 0}; int dy[4] = {0, 0, -1, 1}; int okay(int y, int x){ if(y >= 0 && x >= 0 && y < N && x < M){ //cout << y << " " << x << " " << visited[y][x] << endl; if(visited[y][x] == 0) return 1; } return 0; } void dfs(int y, int x, int depth, int sum){ //cout << y << " " << x << " " << depth << endl; if(depth == 4){ if(sum > result) result = sum; return; } for(int i = 0; i < 4; i++){ if(okay(y+dy[i], x+dx[i])){ visited[y+dy[i]][x+dx[i]] = 1; dfs(y+dy[i], x+dx[i], depth+1, sum+matrix[y+dy[i]][x+dx[i]]); visited[y+dy[i]][x+dx[i]] = 0; } //else cout << y+dy[i] << " " << x+dx[i] << " " << "no\n"; } } int main(){ ios::sync_with_stdio(0); cin.tie(0); N, M; cin >> N >> M; matrix = new int*[N]; for(int i = 0; i < N; i++){ matrix[i] = new int[M]; } visited = new int*[N]; for(int i = 0; i < N; i++){ visited[i] = new int[M]; } for(int i = 0; i < N; i++){ for(int j = 0; j < M; j++){ cin >> matrix[i][j]; visited[i][j] = 0; } } result = -1; for(int i = 0; i < N; i++){ for(int j = 0; j < M; j++){ sum = matrix[i][j]; visited[i][j] = 1; dfs(i, j, 1, sum); visited[i][j] = 0; } } int tmp, mintmp = 0; for(int i = 0; i < N; i++){ for(int j = 0; j < M; j++){ tmp = matrix[i][j]; if(i == 0) mintmp = matrix[i+1][j]; else mintmp = matrix[i-1][j]; for(int k = 0; k < 4; k++){ if(okay(i+dy[k], j+dx[k])){ tmp += matrix[i+dy[k]][j+dx[k]]; if(matrix[i+dy[k]][j+dx[k]] < mintmp) mintmp = matrix[i+dy[k]][j+dx[k]]; } else break; } sum = tmp - mintmp; if(sum > result) result = sum; } } // visited[0][0] =1; // dfs(0, 0, 1, matrix[0][0]); cout << result; }

제출 #30276

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: