[골4] 14500 - 테트로미노

#include <iostream>
#include <limits.h>
#include <algorithm>
#include <vector>
#include <queue>	

using namespace std;
using ll = long long;

#pragma region 상하좌우 / 위치

const pair<int, int> dir[]
{
	{  1,  0 },
	{ -1,  0 },
	{  0, -1 },
	{  0,  1 },
};

#define _y first
#define _x second

#pragma endregion

#pragma region 빠른 입출력

#define FAST_IO() \
{\
	ios::sync_with_stdio(false);\
	cin.tie(NULL); \
	cout.tie(NULL); \
}\

#pragma endregion

#define MAX 501

vector<vector<bool>> vis;
vector<vector<int>> map;
int n, m, res;

void DFS(int y, int x, int cnt, int sum)
{
	if (cnt == 4)
	{
		res = max(res, sum);
		return;
	}
	for (int i = 0; i < 4; i++)
	{
		int ny = y + dir[i]._y, nx = x + dir[i]._x;

		if (nx < 0  ||
			ny < 0  ||
			nx >= m ||
			ny >= n)
			continue;

		if (vis[ny][nx])
			continue;

		vis[ny][nx] = true;		
		DFS(ny, nx, cnt + 1, sum + map[ny][nx]);
		DFS(y, x,	cnt + 1, sum + map[ny][nx]);
		vis[ny][nx] = false;
	}
}

int main()
{
	FAST_IO();

	cin >> n >> m;
	map.resize(n, vector<int>(m));
	vis.resize(n, vector<bool>(m));

	for (int y = 0; y < n; y++)
	{
		for (int x = 0; x < m; x++)
			cin >> map[y][x];
	}
	for (int y = 0; y < n; y++)
	{
		for (int x = 0; x < m; x++)
		{
			vis[y][x] = true;
			DFS(y, x, 1, map[y][x]);
			vis[y][x] = false;
		}
	}
	cout << res;
}

 

 

참고

[Algorithm] 백준 14500 테트로미노 - C++, DFS :: 껍데기방 (tistory.com)