## 3808: Neerc2012 Labyrinth of the Minotaur

2017年10月16日 ⁄ 综合 ⁄ 共 2252字 ⁄ 字号 评论关闭

n<=1500 m<=1500

```#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;
}```