#include #include #include #include #include #include using namespace std; int N,M, answer = 0; int map[501][501]; bool visit[501][501] = { false }; int dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 }; void block(int x, int y) { // 보라 블럭 //answer = max({ answer, map[x][y] + map[x - 1][y] + map[x - 1][y - 1] + map[x - 1][y + 1], map[x][y] + map[x + 1][y] + map[x + 1][y - 1] + map[x + 1][y + 1], // map[x][y] + map[x][y - 1] + map[x - 1][y - 1] + map[x + 1][y - 1], map[x][y] + map[x][y + 1] + map[x - 1][y + 1] + map[x + 1][y + 1], // map[x][y] + map[x - 1][y] + map[x][y - 1] + map[x][y + 1], map[x][y] + map[x + 1][y] + map[x][y - 1] + map[x][y + 1], // map[x][y] + map[x - 1][y] + map[x + 1][y] + map[x][y + 1], map[x][y] + map[x - 1][y] + map[x + 1][y] + map[x][y - 1]}); if (x + 2 < N && y - 1 >= 0) { int now = map[x][y] + map[x + 1][y] + map[x + 2][y] + map[x + 1][y - 1]; answer = max(now, answer); } if (x + 2 < N && y + 1 < M) { int now = map[x][y] + map[x + 1][y] + map[x + 2][y] + map[x + 1][y + 1]; answer = max(now, answer); } if (x - 1 > 0 && y + 2 < M) { int now = map[x][y] + map[x][y + 1] + map[x][y + 2] + map[x - 1][y + 1]; answer = max(now, answer); } if (x + 1 < N && y + 2 < M) { int now = map[x][y] + map[x][y + 1] + map[x][y + 2] + map[x + 1][y + 1]; answer = max(now, answer); } } void DFS(int x, int y, int sum, int now) { if (now == 4) { answer = max(answer, sum); return; } for (int i = 0; i < 4; i++) { int nx = x + dx[i], ny = y + dy[i]; if (nx >= 0 && nx < N && ny >= 0 && ny < M) { if (!visit[nx][ny]) { visit[nx][ny] = true; DFS(nx, ny, sum + map[nx][ny], now + 1); visit[nx][ny] = false; } } } } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cin >> N >> M; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { cin >> map[i][j]; } } for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { int sum = map[i][j], now = 1; visit[i][j] = true; DFS(i, j, sum, now); visit[i][j] = false; block(i, j); } } cout << answer; return 0; }

제출 #39598

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: