ABC 129 D - Lamp

atcoder.jp

AtCoder Beginner Contest129 D - Lamp

問題概要

H行W列のマップが与えられ、マップは壁か地面。
壁に当たるまで直進する光を放つランプをどこかに置き、できるだけ多くのマスを照らしたい。

考えたこと

縦横四方向にできるだけ地続きな場所を探したい。
幅優先で探すことを考えたけど、全部のマスに幅優先していては間に合わない。
求めたいのは「どれだけ地面が続いているか」なので、累積和が使えそう。

解法

縦方向・横方向の累積和をそれぞれ求め、最後に足し合わせると良い。
例えば

4 6
#..#..
.....#
....#.
#.#...

という入力なら

//縦方向
011011
122120
233201
040312

//横方向
012012
123450
123401
010123

という風にした後、それぞれのマスについて、「その領域での最大値」に置き換えてやると良い。

//縦方向
043021
243320
243302
040312

//横方向
022022
555550
444401
010333

という風なデータ構造を作れば、あとはそれぞれのマスについて縦方向累積和と横方向累積和を足し合わせて、最後に-1すれば良い（中心のマスを2回カウントしてしまうため）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(void){
	int h,w;
	cin>>h>>w;
	char s[h][w];
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			cin>>s[i][j];
		}
	}
	int hsum[h][w],wsum[h][w];
	memset(hsum,0,sizeof(hsum));
	memset(wsum,0,sizeof(wsum));
	int cnt=0;
       //縦方向の累積和を求める
	for(int i=0;i<w;i++){
		for(int j=0;j<h;j++){
			if(s[j][i]=='#'){
				hsum[j][i]=0;
			}else{
				if(j!=0)hsum[j][i]=hsum[j-1][i]+1;
				else hsum[j][i]=1;
			}
		}
	}
       //横方向の累積和を求める
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			if(s[i][j]=='#'){
				wsum[i][j]=0;
			}else{
				if(j!=0)wsum[i][j]=wsum[i][j-1]+1;
				else wsum[i][j]=1;
			}
		}
	}
       //累積和をそれぞれ、その領域での最大値に置き換える
	for(int i=0;i<w;i++){
		int tmp=hsum[h-1][i];
		for(int j=h-1;j>=0;j--){
			if(s[j][i]=='#'){
				tmp = hsum[j-1][i];
			}else{
				hsum[j][i]=tmp;
			}
		}
	}
	for(int i=0;i<h;i++){
		int tmp=wsum[i][w-1];
		for(int j=w-1;j>=0;j--){
			if(s[i][j]=='#'){
				tmp = wsum[i][j-1];
			}else{
				wsum[i][j]=tmp;
			}
		}
	}
	int res =0;
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			res = max(res,hsum[i][j]+wsum[i][j]);
		}
	}
	cout<<res-1<<endl;
}