Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

int n,m,t;

#define MAXN 110

inline char getc()

{

	register char c = getchar();

	while(c != '.' && c != '#')c = getchar();

	return c;

}

bool ava[MAXN][MAXN];

char p[MAXN][MAXN];

int d[MAXN * 4][MAXN * 4];

int dis[MAXN][MAXN][4];

bool inq[MAXN][MAXN];

inline int to(int i,int j){return (i - 1) * 4 + j;}

#define MAXT 16

int px[MAXT],py[MAXT];

int sx,sy;

#define fi first

#define se second

bool v[MAXN * 4];

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

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

inline void bfs(int x,int y,int id)

{

	if(!ava[x][y])return;

	memset(dis,0x3f,sizeof(dis));

	for(register int k = 0;k < 4;++k)dis[x][y][k] = 0;

	inq[x][y] = true;

	queue< pair<int,int> > q;

	q.push(make_pair(x,y));

	while(!q.empty())

	{

		register int kx = q.front().fi,ky = q.front().se;q.pop();

		inq[kx][ky] = false;

		for(register int k = 0;k < 4;++k)

		{

			register int nx = kx + movex[k],ny = ky + movey[k];

			if(!ava[nx][ny])continue;

			for(register int b = 0;b < 4;++b)

			{

				if(dis[nx][ny][b] > dis[kx][ky][k] + (k != b))

				{

					dis[nx][ny][b] = dis[kx][ky][k] + (k != b);

					if(!inq[nx][ny])

					{

						inq[nx][ny] = true;

						q.push(make_pair(nx,ny));

					}

				}

			}

		}

	}

	for(register int i = 1;i <= t;++i)

	{

		for(register int k = 0;k < 4;++k)

		{

			register int nx = px[i] + movex[k],ny = py[i] + movey[k];

			for(register int b = 0;b < 4;++b)

				d[id][to(i,k)] = min(d[id][to(i,k)],dis[nx][ny][b] + (nx + movex[b] != px[i] || ny + movey[b] != py[i]));

		}

	}

	return;

}

int f[1 << MAXT][MAXT][4];

int main()

{

	scanf("%d%d%d",&n,&m,&t);

	memset(ava,false,sizeof(ava));

	for(register int i = 1;i <= n;++i)

	{

		for(register int j = 1;j <= m;++j)

		{

			p[i][j] = getc();

			if(p[i][j] == '.')ava[i][j] = true;

		}

	}

	for(register int i = 1;i <= t;++i)scanf("%d%d",&px[i],&py[i]);

	scanf("%d%d",&sx,&sy);

	memset(d,0x3f,sizeof(d));

	for(register int i = 1;i <= t;++i)

		for(register int k = 0;k < 4;++k)

			bfs(px[i] + movex[k],py[i] + movey[k],to(i,k));

	bfs(sx,sy,4 * t);

	memset(f,0x3f,sizeof(f));

	for(register int i = 1;i <= t;++i)

		for(register int k = 0;k < 4;++k)

			f[1 << (i - 1)][i][k] = d[4 * t][to(i,k)] + 1;

	register int tot = (1 << t) - 1;

	for(register int b = 1;b <= tot;++b)

		for(register int i = 1;i <= t;++i)

			if(b & (1 << (i - 1)))

				for(register int k = 0;k < 4;++k)

					for(register int j = 1;j <= t;++j)

						for(register int l = 0;l < 4;++l)

							if(f[b | (1 << (j - 1))][j][l] > f[b][i][k] + d[to(i,k)][to(j,l)] + 1)

								f[b | (1 << (j - 1))][j][l] = f[b][i][k] + d[to(i,k)][to(j,l)] + 1;

	register int ans = 0x3f3f3f3f;

	for(register int i = 1;i <= t;++i)

		for(register int k = 0;k < 4;++k)

			ans = min(ans,f[tot][i][k]);

	cout << ans << endl;

	return 0;

}