14500번 테트로미노

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
int map[501][501];
int ch[501][501];
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
using namespace std;
int n, m, res=4;

void DFS(int x, int y, int cnt, int sum) {
	//printf("%d %d %d %d\n", x, y, cnt, sum);
	if (cnt==4) {
		if (sum > res) res = sum;
	}
	else {
		for (int i = 0; i < 4; i++) {
			int xx = x + dx[i];
			int yy = y + dy[i];
			if (xx > n || xx<1 || yy>m || yy < 1) continue;
			if (ch[xx][yy] == 0) {
				ch[xx][yy] = 1;
				DFS(xx, yy, cnt + 1, sum + map[xx][yy]);
				ch[xx][yy] = 0;
			}
		}	
	}
}
int main() {
	int i, j;
	//freopen("in1.txt", "rt", stdin);
	scanf("%d %d", &n, &m);
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= m; j++) {
			scanf("%d", &map[i][j]);
		}
	}
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= m; j++) {
			ch[i][j] = 1;
			DFS(i, j, 1, map[i][j]);
			if (i - 1 >= 1 && j + 1 <= m && j - 1 >= 1 )  res = max(res,map[i][j] + map[i - 1][j] + map[i][j + 1] +  map[i][j - 1]);
			if (i - 1 >= 1 && j + 1 <= m  && i + 1 <= n)  res = max(res,map[i][j] + map[i - 1][j] + map[i][j + 1] + map[i + 1][j]) ;
			if ( j + 1 <= m && j - 1 >= 1 && i + 1 <= n)  res = max(res,map[i][j]  + map[i][j + 1] + map[i + 1][j] + map[i][j - 1]);
			if (i - 1 >= 1 &&  j - 1 >= 1 && i + 1 <= n)  res = max(res,map[i][j] + map[i - 1][j]  + map[i + 1][j] + map[i][j - 1]);
			ch[i][j] = 0;
		}
	}
	printf("%d\n", res);
	return 0;
}