백준 테트로미노

백준 테트로미노 문제에서 결국 DFS  로 ㅜ 자 글자 말고 DFS로 해결 

여기서 가장 어려웠던부분은 DFS 짜로 ㅜ 자 글자 돌려서 돌려 보는거 

그리고 그걸 각각의 dx / dy 배열로 만들어서 정리하는것이 중요 

int X, Y;
int data[501][501];
bool visit[501][501] = { false, };
int dy[4] = { 1, -1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };

// ㅓ ㅗ ㅏ ㅜ 순서대로 // 
int sx[4][4] = { { 0, 0, -1 }, { 0, -1, 1 }, { 0, 0, 1 }, { 0, -1, 1 } };
int sy[4][3] = { { 1, 2, 1 }, { 1, 0, 0 }, { 1, 2, 1 }, { 1, 1, 1 } };

int ans = 0;


bool chk(int x, int y){

	if (x < 0 || x >= X || y < 0 || y >= Y)
		return false;

	return true;
}


void recursive(int x, int y, int n, int total){
	
	if (n >= 4){
		ans = max(ans, total);
		return;
	}
	for (int i = 0; i < 4; i++){
		int nx = x + dx[i];
		int ny = y + dy[i];

		if (chk(nx, ny)){
			if (!visit[ny][nx]){

				visit[ny][nx] = true;
				recursive(nx, ny, n+1, total + data[ny][nx]);
				visit[ny][nx] = false;
			}
		}
	}
}

void other(int x, int y){

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

		int total = data[y][x];
		bool chk_flag = false;
		for(int k = 0; k < 3; k++){

			int nx = x + sx[i][k];
			int ny = y + sy[i][k];

			if (!chk(x, y)){
				chk_flag = true;
				break;
			}

			total += data[ny][nx];
		}

		if (chk_flag) continue;
		ans = max(ans, total);
	}
}
int main() {

	int TC = 1;
	freopen("input16.txt", "r", stdin);	setbuf(stdout, NULL);  cin >> TC;
	 
	while (TC--)
	{
		ans = 0;
		cin >> Y >> X;

		for (int i = 0; i < Y; i++)
		for (int j = 0; j < X; j++)
			cin >> data[i][j], visit[i][j] = false;

	
		for (int i = 0; i < Y; i++){
			for (int j = 0; j < X; j++){
				visit[i][j] = true;
				recursive(j, i, 1, data[i][j]);

				other(j, i);
				visit[i][j] = false;

			}
		}
		cout << ans << endl;

	}
	return 0;
}