프로젝트 오일러 문제 11

Largest product in a grid

Problem 11

In the 20×20 grid below, four numbers along a diagonal line have been marked in red.

08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

The product of these numbers is 26 × 63 × 78 × 14 = 1788696.

What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20×20 grid?

20x20 격자 속에서 한 방향으로 4개 연속 이어진 수의 곱이 가장 큰 수는 무엇인가.

8방향 탐색에 대해 묻는 문제다. 다만 곱셈을 구하는 문제이므로 4방향만 탐색해도 된다. 또, 연속된 4개의 수가 필요하므로 탐색범위는 0~19가 아닌 0~16으로 조정된다.

int Problem011()
{
	std::ifstream file("Project_Euler_011.txt");
	if (!file.is_open())
	{
		return -1;
	}
	const int SIZE = 20;
	int** numArr = new int*[SIZE];
	for (int i = 0; i < SIZE; i++)
	{
		numArr[i] = new int[SIZE];
	}
	for (int i = 0; i < SIZE; i++)
	{
		for (int j = 0; j < SIZE; j++)
		{
			file >> numArr[i][j];
		}
	}
	file.close();

	int ret = 0;
	for (int x = 0; x < SIZE - 3; x++)
	{
		for (int y = 0; y < SIZE - 3; y++)
		{
			if (numArr[x][y] == 0)
			{
				continue;
			}
			for (int i = -1; i <= 1; i++)
			{
				for (int j = 0; j <= 1; j++)
				{
					if (i == 0 && j == 0 || i == -1 && j == 0)
					{
						continue;
					}
					if (x < 3 && i == -1)
					{
						continue;
					}
					int currentValue = 1;
					for (int n = 0; n < 4; n++)
					{
						if (numArr[x + i * n][y + j * n] == 0)
						{
							currentValue = 0;
							break;
						}
						currentValue = currentValue * numArr[x + i * n][y + j * n];
					}
					if (currentValue > ret)
					{
						ret = currentValue;
					}
				}
			}
		}
	}
	for (int i = 0; i < SIZE; i++)
	{
		delete[] numArr[i];
	}
	delete[] numArr;
	return ret;
}