#include #include #include #include using namespace std; struct Point { pair pos; int value; Point(pair p, int v) : pos(p), value(v) {} bool operator<(const Point& other) const { return value < other.value; } }; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; int N, M, max_value; vector> map; vector> visited; vector> visited_pos; void input_data() { cin >> N >> M; map.resize(N, vector(M)); visited.resize(N, vector(M, false)); for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { cin >> map[i][j]; } } } void get_max_value(int y, int x) { visited[y][x] = true; visited_pos.push_back({y, x}); int cur_value = 0; priority_queue pq; pq.push(Point({y, x}, map[y][x])); for(int i = 0; i < 4; i++) { Point cur = pq.top(); cur_value += cur.value; // cout << "i: " << cur.pos.first << " j: " << cur.pos.second << " cur_value: " << cur.value << "\n"; pq.pop(); for(int j = 0; j < 4; j++) { int ny = cur.pos.first + dy[j]; int nx = cur.pos.second + dx[j]; if(ny < 0 || ny >= N || nx < 0 || nx >= M) continue; else if(visited[ny][nx]) continue; pq.push(Point({ny, nx}, map[ny][nx])); visited[ny][nx] = true; visited_pos.push_back({ny, nx}); } } if(x + 4 < M) cur_value = max(cur_value, map[y][x] + map[y][x+1] + map[y][x+2] + map[y][x+3]); if(y + 4 < N) cur_value = max(cur_value, map[y][x] + map[y+1][x] + map[y+2][x] + map[y+3][x]); // 배열 초기화. while(!visited_pos.empty()) { pair cur = visited_pos.back(); visited[cur.first][cur.second] = false; visited_pos.pop_back(); } // cout << "result : i: " << y << " j: " << x << " cur_value: " << cur_value << "\n-------------\n"; max_value = max(max_value, cur_value); } void solution(){ for(int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { get_max_value(i, j); } } } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); input_data(); solution(); cout << max_value; return 0; }

제출 #81288

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력: