글 읽기 - 맵을 돌리는 방식으로 문제를 풀고 있는데 반례를 모르곘습니다

bonitoyur 5년 전 0

블럭은 그대로 두고

맵 전체를 90,180,270, 상하 대칭, 좌우 대칭, 90도 회전 후 상하 대칭, 90도 돌린 후 좌우 대칭

이렇게 총 8개의 맵에 블럭을 하나씩 대입하는 방법을 생각해서 구현을 하였는데

반례를 못찾겠습니다ㅠㅠ!

혹시 제 아이디어가 아예 잘못 됬을까요??

8개의 맵을 그려 놓고 나오는 도형의 모양을 원본 맵에 맞춰서 비교해 보니까 총 19가지가 나왔었습니다.

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

int N, M;
int map[600][600];
int map90[600][600], map180[600][600], map270[600][600];
int mapRL[600][600], mapUD[600][600];
int map90RL[600][600], map90UD[600][600];


void map_90() // ok
{
	for (int i = 1; i <= M; i++)
		for (int j = 1; j <= N; j++)
			map90[i][j] = map[N-j+1][i];
}

void map_180() // ok
{
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
			map180[i][j] = map[N-i+1][M-j+1];
}

void map_270() // ok
{
	for (int i = 1; i <= M; i++)
		for (int j = 1; j <= N; j++)
			map270[i][j] = map180[N-j+1][i];

}

void map_RL() //ok
{
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
			mapRL[i][j] = map[i][M - j + 1];

}

void map_UD() //ok
{
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
			mapUD[i][j] = map[N - i + 1][j];
}

void map_90RL()//ok
{
	for (int i = 1; i <= M; i++)
		for (int j = 1; j <= N; j++)
			map90RL[i][j] = map90[i][N-j+1];

}

void map_90UD()//ok
{
	for (int i = 1; i <= M; i++)
		for (int j = 1; j <= N; j++)
			map90UD[i][j] = map90[M-i+1][j];
}

int block1(int arr[600][600], int x, int y) // ㅡ 모양
{
	int cnt1 = 0;
	cnt1 = cnt1 + arr[x][y] + arr[x][y + 1] + arr[x][y + 2] + arr[x][y + 3];
	//cout << "1번블럭" << cnt1 << endl;
	return cnt1;
}

int block2(int arr[600][600], int x, int y) // ㅁ모양
{
	int cnt2 = 0;
	cnt2 = cnt2 + arr[x][y] + arr[x][y + 1] + arr[x + 1][y] + arr[x + 1][y + 1];
	//cout << "2번블럭" << cnt2 << endl;
	return cnt2;

}

int block3(int arr[600][600], int x, int y) // ㄴ모양
{
	int cnt3 = 0;
	cnt3 = cnt3 + arr[x][y] + arr[x + 1][y] + arr[x + 2][y] + arr[x + 2][y + 1];
	//cout << "3번블럭" << cnt3 << endl;
	return cnt3;
}

int block4(int arr[600][600], int x, int y) // 번개 모양
{
	int cnt4 = 0;
	cnt4 = cnt4 + arr[x][y] + arr[x + 1][y] + arr[x + 1][y + 1] + arr[x + 2][y + 1];
	//cout << "4번블럭" << cnt4 << endl;
	return cnt4;
}

int block5(int arr[600][600], int x, int y) //ㅜ모양
{
	int cnt5 = 0;
	cnt5 = cnt5 + arr[x][y] + arr[x][y + 1] + arr[x + 1][y + 1] + arr[x][y + 2];
	//cout << "5번블럭" << cnt5 << endl;
	return cnt5;
}

int main()
{
	int res1, res2;
	cin >> N >> M;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
			cin >> map[i][j];
	int ans0, ans90, ans180, ans270, ansRL, ansUD, ans90RL, ans90UD;

	map_90();
	map_180();
	map_270();
	map_RL();
	map_UD();
	map_90RL();
	map_90UD();

	int ans1 = 0, ans2 = 0;
	for (int i = 1; i <= N; i++) // 원본, 180도 회전한 map 에서의 테트로미노
	{
		for (int j = 1; j <= M; j++)
		{
			int temp0 = max(max(block1(map, i, j), block2(map, i, j)), max(block3(map, i, j), block4(map, i, j)));
			ans0 = max(temp0, block5(map, i, j));

			int temp180 = max(max(block1(map180, i, j), block2(map180, i, j)), max(block3(map180, i, j), block4(map180, i, j)));
			ans180 = max(temp180, block5(map180, i, j));
			//cout << i << " " << j << "출발 : " << ans0 << " " << ans180 << endl;

			int tempRL = max(max(block1(mapRL, i, j), block2(mapRL, i, j)), max(block3(mapRL, i, j), block4(mapRL, i, j)));
			ansRL = max(tempRL, block5(mapRL, i, j));

			int tempUD = max(max(block1(mapUD, i, j), block2(mapUD, i, j)), max(block3(mapUD, i, j), block4(mapUD, i, j)));
			ansUD = max(tempUD, block5(mapUD, i, j));

			ans1 = max(max(ans0, ans180), max(ansRL, ansUD));
			res1 = max(res1, ans1);
		}

	}

	for (int i = 1; i <= M; i++) //90도, 270도 회전한 map 에서의 테트로미노
	{
		for (int j = 1; j <= N; j++)
		{
			int temp90 = max(max(block1(map90, i, j), block2(map90, i, j)), max(block3(map90, i, j), block4(map90, i, j)));
			ans90 = max(temp90, block5(map90, i, j));

			int temp270 = max(max(block1(map270, i, j), block2(map270, i, j)), max(block3(map270, i, j), block4(map270, i, j)));
			ans270 = max(temp270, block5(map270, i, j));

			//	cout << i << " " << j << "출발 : " << ans90 << " " << ans270 << endl;

			int temp90RL = max(max(block1(map90RL, i, j), block2(map90RL, i, j)), max(block3(map90RL, i, j), block4(map90RL, i, j)));
			ans90RL = max(temp90RL, block5(map90RL, i, j));

			int temp90UD = max(max(block1(map90UD, i, j), block2(map90UD, i, j)), max(block3(map90UD, i, j), block4(map90UD, i, j)));
			ans90UD = max(temp90UD, block5(map90UD, i, j));

			ans2 = max(max(ans90, ans270), max(ans90RL, ans90UD));
			res2 = max(res2, ans2);

		}
	}
	int result = max(res1, res2);
	cout << result << endl;

	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

맵을 돌리는 방식으로 문제를 풀고 있는데 반례를 모르곘습니다

bonitoyur 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말