#include using namespace std ; typedef long long ll ; typedef pair pii ; vector > node ; vector > visited ; int n, m ; int dx[4] = {-1, 1, 0, 0} ; int dy[4] = {0, 0, 1, -1} ; struct info { int y ; int x ; int cnt = 0 ; int sum = 0 ; } ; queue q ; int Mx = 0 ; void BFS(int a, int b) { while ( !q.empty() ) { info temp = q.front() ; q.pop() ; int y = temp.y ; int x = temp.x ; visited[y][x] = 1 ; Mx = max(Mx, temp.sum) ; if ( temp.cnt == 3 ) continue ; for ( int i = 0 ; i < 4 ; i ++ ) { int yy = y + dy[i] ; int xx = x + dx[i] ; if ( xx < 0 || yy < 0 || xx >= m || yy >= n ) continue ; if ( xx >= b+4 || yy >= a+4 || visited[yy][xx] ) continue ; q.push({yy, xx, temp.cnt + 1, temp.sum + node[yy][xx]}) ; // cout << temp.sum + node[yy][xx] << "\n" ; // cout << temp.cnt+1 << " : " << temp.sum << " + " << node[yy][xx] << " = " << temp.sum + node[yy][xx] << "\n" ; } } } void DFS(info temp) { int y = temp.y ; int x = temp.x ; visited[y][x] = 1 ; Mx = max(Mx, temp.sum) ; if ( temp.cnt == 3 ) continue ; for ( int i = 0 ; i < 4 ; i ++ ) { int yy = y + dy[i] ; int xx = x + dx[i] ; if ( yy < 0 || yy >= n || xx < 0 || xx >= m ) continue ; if ( visited[yy][xx] ) continue ; // cout << temp.cnt+1 << " : " << temp.sum << " + " << node[yy][xx] << " = " << temp.sum + node[yy][xx] << "\n" ; DFS({yy, xx, temp.cnt + 1, temp.sum + node[yy][xx]}) ; } } int main() { cin.tie(0)->sync_with_stdio(false) ; cin >> n >> m ; node.resize(n+1, vector (m+1, 0)) ; visited.resize(n+1, vector (m+1, 0)) ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < m ; j ++ ) { cin >> node[i][j] ; } } // q.push({1, 0, 0, node[1][0]}) ; // BFS(1, 0) ; // DFS({0, 4, 0, node[0][4]}) ; for ( int y = 0 ; y < n ; y ++ ) { for ( int x = 0 ; x < m ; x ++ ) { vector v ; for ( int i = 0 ; i < 4 ; i ++ ) { int yy = y + dy[i] ; int xx = x + dx[i] ; if ( xx < 0 || yy < 0 || xx >= m || yy >= n ) continue ; v.push_back(node[yy][xx]) ; } if ( v.size() >= 3 ) { sort(v.begin(), v.end(), greater<>()) ; Mx = max(Mx, node[y][x] + v[0] + v[1] + v[2]) ; } if ( y == n-1 || x == m-1 ) continue ; Mx = max(Mx, node[y][x] + node[y+1][x] + node[y][x+1] + node[y+1][x+1]) ; } } for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < m ; j ++ ) { visited.clear() ; visited.resize(n+1, vector (m+1, 0)) ; // DFS({i, j, 0, node[i][j]}) ; q.push({i, j, 0, node[i][j]}) ; BFS(i, j) ; } } cout << Mx ; return 0 ; }

제출 #112989

제출 정보

제출 결과

제출 코드

찾은 반례