84 lines
2.4 KiB
C
84 lines
2.4 KiB
C
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <stdbool.h>
|
|
|
|
int max(int a, int b);
|
|
void dfs(int** arr, bool** visited, int x, int y, int n, int m, int currentSum, int* currentMax, int depth);
|
|
void T_block_Search(int** arr, int n, int m, int* currentMax);
|
|
|
|
int main(){
|
|
int N, M;
|
|
scanf("%d %d",&N, &M);
|
|
int** canvas = (int**)malloc(sizeof(int*)*N);
|
|
bool** visited = (bool**)malloc(sizeof(bool*)*N);
|
|
for(int i=0; i<N; i++){
|
|
canvas[i] = (int*)malloc(sizeof(int)*M);
|
|
visited[i] = (bool*)malloc(sizeof(bool)*M);
|
|
for(int j=0; j<M; j++){
|
|
scanf("%d",&canvas[i][j]);
|
|
visited[i][j] = false;
|
|
}
|
|
}
|
|
|
|
int maxValue = 0;
|
|
for(int x=0; x<M; x++){
|
|
for(int y=0; y<N; y++){
|
|
visited[y][x] = true;
|
|
dfs(canvas, visited, x, y, N, M, canvas[y][x], &maxValue, 1);
|
|
visited[y][x] = false;
|
|
}
|
|
}
|
|
|
|
T_block_Search(canvas, N, M, &maxValue);
|
|
|
|
printf("%d\n",maxValue);
|
|
|
|
for(int i=0; i<N; i++){
|
|
free(canvas[i]);
|
|
free(visited[i]);
|
|
}
|
|
free(canvas);
|
|
free(visited);
|
|
|
|
return 0;
|
|
}
|
|
|
|
int max(int a, int b){
|
|
return (a>b) ? a : b;
|
|
}
|
|
|
|
void dfs(int** arr, bool** visited, int x, int y, int n, int m, int currentSum, int* currentMax, int depth){
|
|
if(depth==4) {
|
|
*currentMax = max(currentSum, *currentMax);
|
|
return;
|
|
}
|
|
|
|
int dx[4] = {1,-1,0,0};
|
|
int dy[4] = {0,0,1,-1};
|
|
|
|
for(int i=0; i<4; i++){
|
|
int nx = x + dx[i];
|
|
int ny = y + dy[i];
|
|
|
|
if(nx<0 || ny<0 || nx>=m || ny>=n || visited[ny][nx]) continue;
|
|
|
|
visited[ny][nx] = true;
|
|
dfs(arr, visited, nx, ny, n, m, currentSum + arr[ny][nx], currentMax, depth + 1);
|
|
visited[ny][nx] = false;
|
|
}
|
|
}
|
|
|
|
void T_block_Search(int** arr, int n, int m, int* currentMax){
|
|
for(int y=0; y<n; y++){
|
|
for(int x=0; x<m; x++){
|
|
//ㅏ
|
|
if(x+1<m && y>=1 && y+1<n) *currentMax = max(*currentMax, arr[y][x]+arr[y][x+1]+arr[y-1][x]+arr[y+1][x]);
|
|
//ㅜ
|
|
if(x>=1 && x+1<m && y+1<n) *currentMax = max(*currentMax, arr[y][x]+arr[y][x+1]+arr[y][x-1]+arr[y+1][x]);
|
|
//ㅓ
|
|
if(x>=1 && y>=1 && y+1<n) *currentMax = max(*currentMax, arr[y][x]+arr[y][x-1]+arr[y-1][x]+arr[y+1][x]);
|
|
//ㅗ
|
|
if(x>=1 && x+1<m && y>=1) *currentMax = max(*currentMax, arr[y][x]+arr[y][x+1]+arr[y][x-1]+arr[y-1][x]);
|
|
}
|
|
}
|
|
} |