学步园

题目大意：给你一个n*m的格子，有些格子有障碍，要你找到一个最小的正方形格子，使得这个正方形没有覆盖障碍且去掉这个正方形后（1,1）与（n,m）就不连通了

n<=1500 m<=1500

这题首先要找到从起点到终点的左手路径与右手路径，左手路径就是用左手一直扶着墙壁走，右手路径就是用右手一直扶着墙壁走。如果一个正方形可以覆盖左右手路径就能让他不连通

首先暴搜每个点，把它作为正方形的右上角点，再找到一个最小的边长，mw，使得这个正方形可以阻断（如果任意的合法的mw都不能使得其阻断，就是最大的合法的边长），

如果这个正方形可以阻断，且这个正方形中没有障碍就可以用mw来更新答案了。

我开始的做法是二分找mw，结果发现慢的飞起，是O(n^2logn)的，后来经过仔细研究终于找到了一种去除log的方法

对于一个点(i,j)它的mw是k，那么(i,j+1)的mw<=k+1，这个是很显然的，因为以(i,j+1)为右上角，边长为k+1的正方形是包含以(i,j)为右上角，边长为k的正方形的

所以我们每次求一个点的mw时，就把上一个点的mw+1，在while mw-1也可以阻断路径时就把mw-1，这样就可以求出mw了，因为mw只加了n^2次，所以复杂度是O(n^2)

#include<cmath>
#include<cstdio>
#include<cstring>
#include<cassert>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1511;
const int ax[]={-1,0,1,0},ay[]={0,1,0,-1};
int n,m; char map[maxn][maxn];
void init(){
	scanf("%d%d",&m,&n);
	for (int i=1;i<=n;++i) scanf("%s",map[i]+1);
}
bool vis[maxn][maxn];
inline bool cvis(int x,int y){return x<=n && x>=1 && y<=m && y>=1 && map[x][y]=='.';}
void get(int k,int x,int y,int w){
	while (x!=n || y!=m){
		vis[x][y]=1; int dx,dy,dw;
		dw=(w+k+4)&3,dx=x+ax[dw],dy=y+ay[dw]; if (cvis(dx,dy)) {x=dx,y=dy,w=dw; continue;}
		dw=w,dx=x+ax[dw],dy=y+ay[dw]; if (cvis(dx,dy)) {x=dx,y=dy,w=dw; continue;}
		dw=(w-k+4)&3,dx=x+ax[dw],dy=y+ay[dw]; if (cvis(dx,dy)) {x=dx,y=dy,w=dw; continue;}
		dw=(w+2)&3,dx=x+ax[dw],dy=y+ay[dw]; if (cvis(dx,dy)) {x=dx,y=dy,w=dw; continue;}
	}
}
struct Tmx{
	int a[maxn][maxn];
	void getpxsm(){
		for (int i=1;i<=n;++i) for (int j=1;j<=m;++j)
			a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
	}
	inline int Query(int x1,int y1,int x2,int y2){
		return a[x2][y2]-a[x1][y2]-a[x2][y1]+a[x1][y1];
	}
}mp,lt,rt;
inline bool check(int x,int y,int dx,int dy){
	return (x || y) && (dx!=n || dy!=m) && 
	lt.Query(x,y,dx,dy) && rt.Query(x,y,dx,dy);
}
void work(){
	for (int i=1;i<=n;++i) for (int j=1;j<=m;++j) mp.a[i][j]=map[i][j]=='#';
	mp.getpxsm(); get(-1,1,1,1);
	for (int i=1;i<=n;++i) for (int j=1;j<=m;++j) lt.a[i][j]=vis[i][j]; lt.getpxsm();
	for (int i=1;i<=n;++i) for (int j=1;j<=m;++j) vis[i][j]=0; get(1,1,1,2);
	for (int i=1;i<=n;++i) for (int j=1;j<=m;++j) rt.a[i][j]=vis[i][j]; rt.getpxsm();
	int ans=min(n,m)+1,ax=-1,ay;
	for (int i=1;i<=n;++i){
		int mw=0;
		for (int j=1;j<=m;++j){
			++mw;
			while (mw && (i+mw-1>n || mp.Query(i-1,j-mw,i+mw-1,j))) --mw;
			while (mw>1 && check(i-1,j-mw+1,i+mw-2,j)) --mw;
			if (mw<ans && check(i-1,j-mw,i+mw-1,j)) ans=mw,ax=i,ay=j-mw+1;
		}
	}
	if (ax==-1) puts("Impossible"); else printf("%d %d %d\n",ans,ay,ax);
}
int main(){
	init();
	work();
	return 0;
}