BOJ 14500: 테트로미노

#BOJ 14500: 테트로미노

14500번: 테트로미노

 

#풀이

백트래킹을 이용하여 인접한 4개의 칸을 구할 수 있다.

 

근데 ㅓ,ㅗ,ㅏ,ㅜ 이 모양을 구할 때 조건이 필요하다.

일단 ㅓ를 생각하면 k == 2일 때 칸을 하나 더 추가하고 다시 제자리로 돌아오면 된다.

 

#코드

#include<iostream> // #include<bits/stdc++.h>
using namespace std;
int n, m;
int board[501][501];
int vis[501][501];
int ans;
int num;
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };

void func(int x, int y, int k) {
	if (k == 4) {
		ans = ans < num ? num : ans;
		return;
	}
	
	for (int i = 0; i < 4; i++) {
		int x1 = x + dx[i];
		int y1 = y + dy[i];
		if (x1 < 0 || y1 < 0 || x1 >= n || y1 >= m || vis[x1][y1] != 0)
			continue;
		num = num + board[x1][y1];
		vis[x1][y1] = 1;
		func(x1, y1, k + 1);
		if (k == 2) {
			func(x, y, k + 1);
		}
		num = num - board[x1][y1];
		vis[x1][y1] = 0;
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> board[i][j];
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			num = num + board[i][j];
			vis[i][j] = 1;
			func(i,j, 1);
			num = num - board[i][j];
			vis[i][j] = 0;
		}
	}
	cout << ans << '\n';
	return 0;
}