2333333333333333333333333333333333333333333333
啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊
辣鸡出题人辣鸡出题人辣鸡出题人辣鸡出题人辣鸡出题人辣鸡出题人
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#define inf 1000000007
using namespace std;
int n,m,t,wh[][],dis[][],x[],y[],tab[][][][],pre[][],fro[][][][],f[(<<)+][][];
int dx[]={,-,,,},dy[]={,,,,-};
bool map[][],vis[][];
char s[];
queue <int> q;
void reset()
{
for (int i=;i<=n;i++)
for (int j=;j<=m;j++)
dis[i][j]=inf;
while (!q.empty()) q.pop();
memset(vis,false,sizeof(vis));
}
bool judge(int x,int y)
{
if ((x>=) && (x<=n) && (y>=) && (y<=m) && (!map[x][y]))
return true;
return false;
}
void spfa(int pos,int dir)
{
memset(pre,,sizeof(pre));
if (!judge(x[pos]+dx[dir],y[pos]+dy[dir])) return;
dis[x[pos]+dx[dir]][y[pos]+dy[dir]]=;vis[x[pos]+dx[dir]][y[pos]+dy[dir]]=true;
q.push(x[pos]+dx[dir]);q.push(y[pos]+dy[dir]);
while (!q.empty())
{
int hx,hy;
hx=q.front();q.pop();hy=q.front();q.pop();
int p=;
while (judge(hx-p,hy))
{
if ((dis[hx-p][hy]>dis[hx][hy]+) || ((dis[hx-p][hy]==dis[hx][hy]+) && (wh[hx-p][hy]==)))
{
dis[hx-p][hy]=dis[hx][hy]+;
pre[hx-p][hy]=;
if (!vis[hx-p][hy])
{
vis[hx-p][hy]=true;
q.push(hx-p);q.push(hy);
}
}
p++;
}
p=;
while (judge(hx+p,hy))
{
if ((dis[hx+p][hy]>dis[hx][hy]+) || ((dis[hx+p][hy]==dis[hx][hy]+) && (wh[hx+p][hy]==)))
{
dis[hx+p][hy]=dis[hx][hy]+;
pre[hx+p][hy]=;
if (!vis[hx+p][hy])
{
vis[hx+p][hy]=true;
q.push(hx+p);q.push(hy);
}
}
p++;
}
p=;
while (judge(hx,hy-p))
{
if ((dis[hx][hy-p]>dis[hx][hy]+) || ((dis[hx][hy-p]==dis[hx][hy]+) && (wh[hx][hy-p]==)))
{
dis[hx][hy-p]=dis[hx][hy]+;
pre[hx][hy-p]=;
if (!vis[hx][hy-p])
{
vis[hx][hy-p]=true;
q.push(hx);q.push(hy-p);
}
}
p++;
}
p=;
while (judge(hx,hy+p))
{
if ((dis[hx][hy+p]>dis[hx][hy]+) || ((dis[hx][hy+p]==dis[hx][hy]+) && (wh[hx][hy+p]==)))
{
dis[hx][hy+p]=dis[hx][hy]+;
pre[hx][hy+p]=;
if (!vis[hx][hy+p])
{
vis[hx][hy+p]=true;
q.push(hx);q.push(hy+p);
}
}
p++;
}
vis[hx][hy]=false;
}
}
void get_tab(int pos,int dir)
{
for (int i=;i<=t+;i++)
for (int j=;j<=;j++)
{
if (judge(x[i]+dx[j],y[i]+dy[j]))
{
tab[pos][dir][i][j]=dis[x[i]+dx[j]][y[i]+dy[j]];
fro[pos][dir][i][j]=pre[x[i]+dx[j]][y[i]+dy[j]];
}
}
}
int main()
{
//freopen("secret.in","r",stdin);
//freopen("secret.out","w",stdout);
memset(map,false,sizeof(map));
scanf("%d%d%d",&n,&m,&t);
for (int i=;i<=n;i++)
{
scanf("\n%s",s);
for (int j=;j<m;j++)
if (s[j]=='#') map[i][j+]=true;
}
for (int i=;i<=t;i++)
{
scanf("%d%d",&x[i],&y[i]);
map[x[i]][y[i]]=true;
}
for (int i=;i<=t;i++)
{
for (int j=;j<=;j++)
{
if (judge(x[i]+dx[j],y[i]+dy[j]))
wh[x[i]+dx[j]][y[i]+dy[j]]=j;
}
}
scanf("%d%d",&x[t+],&y[t+]);
for (int i=;i<=t+;i++)
for (int j=;j<=;j++)
for (int k=;k<=t;k++)
for (int l=;l<=;l++)
tab[i][j][k][l]=inf;
for (int i=;i<=t;i++)
{
for (int j=;j<=;j++)
{
reset();
spfa(i,j);
get_tab(i,j);
}
}
reset();
spfa(t+,);
for (int i=;i<=t+;i++)
for (int j=;j<=;j++)
{
if (judge(x[i]+dx[j],y[i]+dy[j]))
{
tab[t+][][i][j]=dis[x[i]+dx[j]][y[i]+dy[j]];
fro[t+][][i][j]=pre[x[i]+dx[j]][y[i]+dy[j]];
}
}
int top=(<<t)-;
for (int s=;s<=top;s++)
for (int i=;i<=t;i++)
for (int j=;j<=;j++)
f[s][i][j]=inf;
for (int i=;i<=t;i++)
for (int j=;j<=;j++)
{
if (fro[t+][][i][j]!=j)
f[<<(i-)][i][j]=tab[t+][][i][j]+;
else f[<<(i-)][i][j]=tab[t+][][i][j];
}
for (int ss=;ss<=top;ss++)
{
for (int i=;i<=t;i++)
{
if (ss&(<<(i-)))
{
for (int j=;j<=t;j++)
{
if (ss&(<<(j-))) continue;
for (int k=;k<=;k++)
for (int l=;l<=;l++)
{
if (tab[i][k][j][l]==inf) continue;
if (fro[i][k][j][l]!=l)
f[ss|<<(j-)][j][l]=min(f[ss|<<(j-)][j][l],f[ss][i][k]+tab[i][k][j][l]+);
else f[ss|<<(j-)][j][l]=min(f[ss|<<(j-)][j][l],f[ss][i][k]+tab[i][k][j][l]);
}
}
}
}
}
int ans=inf;
for (int i=;i<=t;i++)
for (int j=;j<=;j++)
ans=min(ans,f[top][i][j]);
printf("%d\n",ans);
return ;
}