ABC_129_D - Lamp

[zeikar]

Problem link

https://atcoder.jp/contests/abc129/tasks/abc129_d

Problem Summary

H * W 크기의 그리드가 있고 빈 칸에 램프를 놓을 수 있다.
램프는 장애물을 넘을 수 없고, 상하좌우를 밝힐 수 있다.
램프가 밝힐 수 있는 칸의 최대 수를 구하는 문제.

Solution

아주 간단하게 완전 탐색하면 시간 초과다. (모든 점에 램프를 넣어보고 칸 수를 계산)
빛이 비출 수 있는 칸 수를 계산할 때 시간을 줄일 수 있는데, 칸 별로 연속한 칸 수를 저장해두면 된다.
상하로 연속한 칸의 개수, 좌우로 연속한 칸의 개수를 미리 계산해서 넣어둔 후 마지막엔 두 합이 최대가 되는 것이 정답이다.

Source Code

#include <iostream>
#include <string>
using namespace std;

string grid[2000];
int consecutiveX[2000][2000];
int consecutiveY[2000][2000];

int main() {
	int H, W;

	cin >> H >> W;

	for (int i = 0; i < H; i++)
	{
		cin >> grid[i];
	}

	int ans = 0;
	int cnt = 0;

	for (int i = 0; i < H; i++)
	{
		int startX = i, startY = 0;

		for (int j = 0; j < W; j++)
		{
			if (grid[i][j] == '.')
			{
				++cnt;
			}
			else
			{
				for (int k = startY; k < j; k++)
				{
					consecutiveX[startX][k] = cnt;
				}

				startY = j + 1;
				cnt = 0;
			}
		}

		for (int k = startY; k < W; k++)
		{
			consecutiveX[startX][k] = cnt;
		}

		cnt = 0;
	}

	for (int j = 0; j < W; j++)
	{
		int startX = 0, startY = j;

		for (int i = 0; i < H; i++)
		{
			if (grid[i][j] == '.')
			{
				++cnt;
			}
			else
			{
				for (int k = startX; k < i; k++)
				{
					consecutiveY[k][startY] = cnt;
				}

				startX = i + 1;
				cnt = 0;
			}
		}

		for (int k = startX; k < H; k++)
		{
			consecutiveY[k][startY] = cnt;
		}

		cnt = 0;
	}

	for (int i = 0; i < H; i++)
	{
		for (int j = 0; j < W; j++)
		{
			ans = max(ans, consecutiveX[i][j] + consecutiveY[i][j] - 1);
		}
	}

	cout << ans << endl;
}