P2130

真是脑袋抽了，还想着用A*做，当然直接寄，34pts。

rt。

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
#define fi first
#define se second
#define tmi(x)	((x)*(x))
int n,m;
char c[N];

int grf[N][N],v[N][N];
bool s[N][N];

struct posi{
	int x,y;
}ed,fa[N][N];

bool operator <(const posi a,const posi b){
	return tmi(abs(a.x-ed.x))+tmi(abs(a.y-ed.y))<tmi(abs(b.x-ed.x))+tmi(abs(b.y-ed.y));
}

typedef pair<int,posi> PII;
typedef pair<int,PII> PIII;

int ti[N],qu[N],hh,tt;
void init(){
	hh=0,tt=-1;
	int nm=max(n,m);
	for(int i=0;(1<<i)<=nm;i++)
		qu[++tt]=(1<<i),ti[(1<<i)]=1;
	while(hh<=tt){
		int nu=qu[hh++];
		for(int i=0,v;nu+(1<<i)<=nm;i++){
			v=nu+(1<<i);
			if(!ti[v])	qu[++tt]=v,ti[v]=ti[nu]+1; 
			else	ti[v]=min(ti[v],ti[nu]+1);
		}
		for(int i=0,v;nu-(1<<i)>=1;i--){
			v=nu-(1<<i);
			if(!ti[v])	qu[++tt]=v,ti[v]=ti[nu]+1; 
			else	ti[v]=min(ti[v],ti[nu]+1);
		}
	}
}

int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

bool flag=false;

posi q[N*N];
void bfs_val(posi st){
	hh=0,tt=-1;
	q[++tt]=st;
	while(hh<=tt){
		posi u=q[hh++];
		for(int i=0,x,y;i<4;i++){
			x=u.x+dx[i],y=u.y+dy[i];
			if(x<1 || x>n || y<1 || y>m)	continue;
			if(s[x][y])	continue;
			if(v[x][y] || (x==st.x && y==st.y))	continue;
			v[x][y]=v[u.x][u.y]+1;
			q[++tt]={x,y};
		}
	}
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=m;j++)
//			printf("%d ",v[i][j]);
//		puts("");
//	}
}

int bfs_ans(posi st){
	
	if(v[st.x][st.y]==0)	return -1;
	
	priority_queue<PIII,vector<PIII>,greater<PIII> > list;
	list.push({v[st.x][st.y],{0,st}});
	while(list.size()){
		PIII u=list.top();
		list.pop();
		
		posi un=u.se.se;
//		printf("%d %d\n",un.x,un.y);
		if(un.x==ed.x && un.y==ed.y)	return u.se.fi;
		
		for(int i=0,x,y,j;i<4;i++){
			x=u.se.se.x+dx[i],y=u.se.se.y+dy[i];
			j=1;
			while(x>=1 && x<=n && y>=1 && y<=m && !s[x][y]){
				list.push({u.se.fi+ti[j]+v[x][y],{u.se.fi+ti[j],{x,y}}});
				j++;x+=dx[i],y+=dy[i];
			}
		}
	}
	return -1;
}

int main(){
	scanf("%d%d",&n,&m);
	memset(grf,0x3f,sizeof grf);
	for(int i=1,l;i<=n;i++){
		scanf("%s",c+0);
		l=strlen(c);
		for(int j=0;j<l;j++){
			if(c[j]=='X')	s[i][j+1]=true;
			else if(c[j]=='#')	ed.x=i,ed.y=j+1;
		}
	}
	init();
	bfs_val({ed.x,ed.y});
	int ans=bfs_ans({1,1});
	printf("%d",ans);
	return 0;
}
/*
5 5
.....
..XXX
..X.#
.....
..... 
*/