급하게임개발

https://www.acmicpc.net/problem/14500

이 문제의  경우 나는 일단 dfs와 ㅗ 모양의 블록을 나눠서 풀었다 .

테트로미노에는 이렇게 현재 블럭이 있는데

빨간색을 제외한 블록들은 dfs로 검색하면 회전까지 나오는 모양 들이다 빨간색으로 둘러싼 모형들을 배열에다 다 넣어서 최대값을 구하는게 해당 문젠데 그후 빨간색으로 둘러친걸 넣어보면서 최대값을 구하면 된다

일단 빨간색을 제외한 코드의 부분은

void dfs(int x, int y, int cnt , int sum) {
	if (cnt == 4) {
		if (sum > maxNum) {
			maxNum = sum;
		}
	}
	else {
		if (canGo(x + 1, y)) {
			isVisited[x + 1][y] = true;
			dfs(x + 1, y, cnt + 1, sum + arr[x+1][y]);
			isVisited[x + 1][y] = false;
		}
		if (canGo(x - 1, y)) {
			isVisited[x - 1][y] = true;
			dfs(x - 1, y, cnt + 1, sum + arr[x-1][y]);
			isVisited[x - 1][y] = false;
		}
		if (canGo(x , y+1)) {
			isVisited[x][y+1] = true;
			dfs(x , y+1, cnt + 1, sum + arr[x][y+1]);
			isVisited[x][y + 1] = false;
		}
		if (canGo(x , y-1)) {
			isVisited[x ][y-1] = true;
			dfs(x , y-1, cnt + 1, sum + arr[x][y-1]);
			isVisited[x][y - 1] = false;
		}
	}
}

이렇게 된다 그이이유는 저위에 빨간색을 제외한 부분들을 회전과 대칭을 고려할경우 dfs로 나오는 모형과 똑같기 떄문이다
그후 빨간색으로 둘러쳐진 모양은 노가다를 했다

void mountatinShape(int startX, int startY) {
	if (canGo(startX + 1, startY) && canGo(startX, startY - 1) && canGo(startX,startY + 1) && canGo(startX, startY)) {
		int sum = 0;
		sum = arr[startX + 1][startY] + arr[startX][startY - 1] + arr[startX][startY + 1] + arr[startX][startY];
		if (sum > maxNum)
			maxNum = sum;
	}
	if (canGo(startX - 1, startY) && canGo(startX, startY - 1) && canGo(startX, startY + 1) && canGo(startX, startY)) {
		int sum = 0;
		sum = arr[startX - 1][startY] + arr[startX][startY - 1] + arr[startX][startY + 1] + arr[startX][startY];
		if (sum > maxNum)
			maxNum = sum;
	}

	if (canGo(startX + 1, startY) && canGo(startX -1, startY) && canGo(startX, startY + 1) && canGo(startX, startY)) {
		int sum = 0;
		sum = arr[startX + 1][startY] + arr[startX-1][startY] + arr[startX][startY + 1] + arr[startX][startY];
		if (sum > maxNum)
			maxNum = sum;
	}
	if (canGo(startX + 1, startY) && canGo(startX - 1, startY) && canGo(startX, startY - 1) && canGo(startX, startY)) {
		int sum = 0;
		sum = arr[startX + 1][startY] + arr[startX - 1][startY] + arr[startX][startY - 1] + arr[startX][startY];
		if (sum > maxNum)
			maxNum = sum;
	}
}

그래서 이두 로직을 합치면서 최댓값을 저장해주면 이문제는 해결이다

#include<iostream>
using namespace std;
int n, m;
int arr[500][500];
bool isVisited[500][500] = { 0, };
int maxNum = 0;
//세로 1자
bool canGo(int px, int py) {
	if (px >= 0 && px < n && py >= 0 && py < m && !isVisited[px][py]) {
		return true;
	}
	else
		return false;
}
void dfs(int x, int y, int cnt , int sum) {
	if (cnt == 4) {
		if (sum > maxNum) {
			maxNum = sum;
		}
	}
	else {
		if (canGo(x + 1, y)) {
			isVisited[x + 1][y] = true;
			dfs(x + 1, y, cnt + 1, sum + arr[x+1][y]);
			isVisited[x + 1][y] = false;
		}
		if (canGo(x - 1, y)) {
			isVisited[x - 1][y] = true;
			dfs(x - 1, y, cnt + 1, sum + arr[x-1][y]);
			isVisited[x - 1][y] = false;
		}
		if (canGo(x , y+1)) {
			isVisited[x][y+1] = true;
			dfs(x , y+1, cnt + 1, sum + arr[x][y+1]);
			isVisited[x][y + 1] = false;
		}
		if (canGo(x , y-1)) {
			isVisited[x ][y-1] = true;
			dfs(x , y-1, cnt + 1, sum + arr[x][y-1]);
			isVisited[x][y - 1] = false;
		}
	}
}

void mountatinShape(int startX, int startY) {
	if (canGo(startX + 1, startY) && canGo(startX, startY - 1) && canGo(startX,startY + 1) && canGo(startX, startY)) {
		int sum = 0;
		sum = arr[startX + 1][startY] + arr[startX][startY - 1] + arr[startX][startY + 1] + arr[startX][startY];
		if (sum > maxNum)
			maxNum = sum;
	}
	if (canGo(startX - 1, startY) && canGo(startX, startY - 1) && canGo(startX, startY + 1) && canGo(startX, startY)) {
		int sum = 0;
		sum = arr[startX - 1][startY] + arr[startX][startY - 1] + arr[startX][startY + 1] + arr[startX][startY];
		if (sum > maxNum)
			maxNum = sum;
	}

	if (canGo(startX + 1, startY) && canGo(startX -1, startY) && canGo(startX, startY + 1) && canGo(startX, startY)) {
		int sum = 0;
		sum = arr[startX + 1][startY] + arr[startX-1][startY] + arr[startX][startY + 1] + arr[startX][startY];
		if (sum > maxNum)
			maxNum = sum;
	}
	if (canGo(startX + 1, startY) && canGo(startX - 1, startY) && canGo(startX, startY - 1) && canGo(startX, startY)) {
		int sum = 0;
		sum = arr[startX + 1][startY] + arr[startX - 1][startY] + arr[startX][startY - 1] + arr[startX][startY];
		if (sum > maxNum)
			maxNum = sum;
	}
}
void tet1(int startX, int startY) {
	isVisited[startX][startY] = true;
	dfs(startX, startY, 1,arr[startX][startY]);
	isVisited[startX][startY] = false;

}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			mountatinShape(i, j);
			tet1(i, j);
		}
	}

	cout << maxNum;
}