백준 14500번 C++

#include<iostream>

#include<algorithm>

using namespace std;

const int MAX = 501;

int n, m;

int arr[MAX][MAX];

int visited[MAX][MAX];

typedef struct {

int a, b;

}Move;

Move mv[4] = { {1,0},{-1,0},{0,1},{0,-1} };

int dfs(int x, int y,int counts) {

if (counts == 4)

return 0;

int ans = 0;

for (int i = 0; i < 4; i++) {

int mx = x + mv[i].a;

int my = y + mv[i].b;

if (mx >= 0 && mx < n&& my >= 0 && my < m) {

if (visited[mx][my] == 0) {

visited[mx][my] = 1;

ans = max(ans, arr[x][y] + dfs(mx, my,counts+1));

visited[mx][my] = 0;

}

}

}

return ans;

}

int shapesum(int x, int y) {

int ans = 0;

if( (y-1)>=0 && (y+1)<m && (x+1)<n )

ans = max(ans, arr[x][y] + arr[x][y-1] + arr[x][y+1] + arr[x+1][y]);

if( (y - 1) >= 0 && (y + 1) < m && (x-1)>=0)

ans = max(ans, arr[x][y] + arr[x][y-1] + arr[x][y+1] + arr[x-1][y]);

if ((x - 1) >= 0 && (x + 1) < n && (y - 1) >= 0)

ans = max(ans, arr[x][y] + arr[x-1][y] + arr[x+1][y] + arr[x][y-1]);

if ((x - 1) >= 0 && (x + 1) < n && (y + 1) <m )

ans = max(ans, arr[x][y] + arr[x-1][y] + arr[x+1][y] + arr[x][y+1]);

return ans;

}

int main(void) {

cin >> n >> m;

for (int i = 0; i < n; i++) {

for (int j = 0; j < m; j++) {

cin >> arr[i][j];

}

}

int maxsum = 0;

for (int i = 0; i < n; i++) {

for (int j=0; j < m; j++) {

visited[i][j] = 1;

maxsum = max(maxsum,dfs(i, j, 0));

maxsum = max(maxsum, shapesum(i, j));

visited[i][j] = 0;

}

}

cout << maxsum << endl;

}