Lamp

Description

你相信光吗？

你相信光会扩散吗？

现在有一个 H×W 的矩阵，其上有一些障碍物。

现在你要往这个矩阵上任意一个非障碍物的地方放置一个灯，

这个灯能向上下左右四个方向放出光，直到碰到障碍物为止。

问当灯放置在哪个位置上时能使灯照射到的方块最多，并输出这个最大值

1 < = H < = 2,000 1 < = W < = 2,000
Format
Input

见样例
Output

如题
Samples
输入数据 1

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

输出数据 1

8

Sol1:
这个题意很简单，如果没什么好的做法，暴力来做
即对于一个空白点，前后左右去扫描，直到遇到故障点或出界。

#include<bits/stdc++.h>
using namespace std;
char h[10000][10000];
int main() {
	int n,m,y=0;
	cin>>n>>m;
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++)
			cin>>h[i][j];
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++) {
			if(h[i][j]!='#') {
				int s=0;
				for(int o=j; o>=1; o--) {
					if(h[i][o]!='.')
						break;
					s++;
				}
				for(int o=j; o<=m; o++) {
					if(h[i][o]!='.')
						break;
					s++;
				}
				for(int o=i; o>=1; o--) {
					if(h[o][j]!='.')
						break;
					s++;
				}
				for(int o=i; o<=n; o++) {
					if(h[o][j]!='.')
						break;
					s++;
				}
				y=max(y,s-3);
			}
		}
	cout<<y;
}

 
细想一下，这样的做法太无趣了，例如对于下面这个数据
#......#
对于夹在两个“＃”之间的6个"."它们左右扩展的长度是一样的
并且扩展的长度其实就是等于其左右两个“#”所在列数的差值再-1

于是我们分行分列进行处理即可，原理是一样的。
即：
我们认为每个“." 是夹在两个故障点之间的，为了保证这个一定成立
我们在整个图形的最外面一圈，全打上故障点。
现在我们对某一行的情况来进行处理，形如下图

我们可以记下这一行的每个故障点所在的列数，即
0，3，7，8
可将其放到一个vector或数组中
接下来我们扫描这一行的所有字符，
for(int i=1;i<=m;i++)

当找到一个点为”."时，设其在第J列
此时我们就要知道这个J是夹0，3，7，8这个数列的哪两个数字之间
实现方法有两种
1：使用两分查找，找第一个严格大于J的数字，则这个数字所代表这个空白点右边的故障点
例如当j=1时，我们找到的数字为3，于是这个空白点能拓展的长度就为3-0-1=2
当j=4时，我们找到的数字为7，于是这个空白点能拓展的长度就为7-3-1=3

2:我们设pos=0,代表我们所找到的空白点至少是处于第0个故障点的右边的
如果在执行
for(int i=1;i<=m;i++)时
如果第j列的点是一个空白点，则它就处于第pos＋１个故障点与第pos个故障点之间
否则 就执行ｐｏｓ＋＋
大 家可手动模拟一下，上面我说的过程 。明显这种方法是强于第1种的，因为它可以直接确定空白点处于哪个故障点的右边