#include<iostream>
#include<queue>
using namespace std;
string s;
int v[1009][1009];
int a[1009][1009],b[1009][1009],c[1009][1009];
int d[20]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096};
int main()
{
	int n,m;
	int e,f;
	cin>>n>>m;
	for (int i=1;i<=n;i++)
	{
		cin>>s;
		for (int j=0;j<m;j++)
		{
			if (s[j]=='.'||s[j]=='X')
			{
				a[i][j+1]=1;
			}
			else if (s[j]=='#')
			{
				e=i;
				f=j+1;
			}
		}
	}
	for (int i=1;i<=n;i++)
	{
		b[i][0]=0;
		for (int j=1;j<=n;j++)
		{
			b[i][j]=a[i][j]+b[i][j-1];
		}
	}
	for (int i=1;i<=n;i++)
	{
		c[i][0]=0;
		for (int j=1;j<=n;j++)
		{
			c[i][j]=a[i][j]+c[i-1][j];
		}
	}
	queue<int>q1;
	q1.push(1);
	queue<int>q2;
	q2.push(1);
	queue<int>q3;
	q3.push(0);
	while (!q1.empty())
	{
		int tmp1=q1.front(),tmp2=q2.front(),tmp3=q3.front();
		q1.pop();
		q2.pop();
		q3.pop();
		if (tmp1==e&&tmp2==f)
		{
			cout<<tmp3<<endl;
			return 0;
		}
		for (int i=0;i<=9;i++)
		{
			int tx=tmp1+d[i],ty=tmp2;
			if (tx>=1&&tx<=n&&ty>=1&&ty<=m&&!v[tx][ty]&&(!a[tx][ty])&&!(c[tx][ty]-c[tmp1][tmp2]))
			{
				v[tx][ty]=1;
				q1.push(tx);
				q2.push(ty);
				q3.push(tmp3+1);
			}
			tx=tmp1;
			ty=tmp2+d[i];
			if (tx>=1&&tx<=n&&ty>=1&&ty<=m&&!v[tx][ty]&&(!a[tx][ty])&&!(b[tx][ty]-b[tmp1][tmp2]))
			{
				v[tx][ty]=1;
				q1.push(tx);
				q2.push(ty);
				q3.push(tmp3+1);
			}
		}
		for (int i=0;i<=9;i++)
		{
			int tx=tmp1-d[i],ty=tmp2;
			if (tx>=1&&tx<=n&&ty>=1&&ty<=m&&!v[tx][ty]&&(!a[tx][ty])&&!(c[tx][ty]-c[tmp1][tmp2]))
			{
				v[tx][ty]=1;
				q1.push(tx);
				q2.push(ty);
				q3.push(tmp3+1);
			}
			tx=tmp1;
			ty=tmp2-d[i];
			if (tx>=1&&tx<=n&&ty>=1&&ty<=m&&!v[tx][ty]&&(!a[tx][ty])&&!(b[tx][ty]-b[tmp1][tmp2]))
			{
				v[tx][ty]=1;
				q1.push(tx);
				q2.push(ty);
				q3.push(tmp3+1);
			}
		}
	}
	cout<<-1<<endl;
	return 0;
}

#1 WA

90分

Wrong Answer.wrong answer On line 1 column 1, read 7, expected 6.

记录