9065云梦瑶 90分求调

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3 * 1e3 + 1000;
long long n,m,k,step1 = -1,step2 = -1,ans = INT_MAX,flag = -1,flag2 = -1;
int dx[4] = {1,-1,0,0},dy[4] = {0,0,-1,1};
long long mapp[maxn][maxn],bfs1_step[maxn][maxn],bfs2_step[maxn][maxn];
bool tp[maxn][maxn],vis[maxn][maxn];
vector <int> h1;
vector <int> h2;
struct coor{int x;int y;};
void bfs1(){
	queue <coor> q1;
	q1.push({1,1});
	vis[1][1] = 1;
	while(!q1.empty()){
		coor now = q1.front();
		int x = now.x,y = now.y;
		if(x == n && y == m) return;
		q1.pop();
		for(int i = 0;i < 4;i++){
			int tx = x + dx[i],ty = y + dy[i];
			if(tx >= 1 && ty >= 1 && tx <= n && ty <= m && vis[tx][ty] != 1 && mapp[tx][ty] != 0){
				vis[tx][ty] = 1;
				bfs1_step[tx][ty] = bfs1_step[x][y] + 1;
				q1.push({tx,ty});
				if(tp[tx][ty] && flag == -1){
					if(step1 == -1){
						step1 = bfs1_step[tx][ty];
						h1.push_back(mapp[tx][ty]);
					}else{
						h1.push_back(mapp[tx][ty]);
					}
				}
			} 
		}
		if(step1 != -1) flag = 0;
	}
}
void bfs2(){
	memset(vis,0,sizeof(vis));
	queue <coor> q2;
	q2.push({n,m});
	vis[n][m] = 1;
	while(!q2.empty()){
		if(step2 != -1 || step2 == 0){
			
			return;
		}
		coor now = q2.front();
		int x = now.x,y = now.y;
		if(x == 1 && y == 1) return;
		q2.pop();
		for(int i = 0;i < 4;i++){
			int tx = x + dx[i],ty = y + dy[i];
			if(tx >= 1 && ty >= 1 && tx <= n && ty <= m && vis[tx][ty] != 1 && mapp[tx][ty] != 0){
				vis[tx][ty] = 1;
				bfs2_step[tx][ty] = bfs2_step[x][y] + 1;
				q2.push({tx,ty});
				if(tp[tx][ty]){
					if(step2 == -1){	
						//cout << tx << "****" << ty << endl;
						step2 = bfs2_step[tx][ty];
						//cout << step2 << endl;
						h2.push_back(mapp[tx][ty]);
					}else{
						//cout << tx << "****" << ty << endl;
						h2.push_back(mapp[tx][ty]);
					}
				}
			} 
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> m >> k;
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= m;j++)
			cin >> mapp[i][j];
	for(int i = 1;i <= k;i++){
		int x,y;
		cin >> x >> y;
		tp[x][y] = 1;
	}
	if(tp[1][1] == 1){step1 = 0;h1.push_back(mapp[1][1]);}
	if(tp[n][m] == 1){step2 = 0;h2.push_back(mapp[n][m]);}
	bfs1();
	if(bfs1_step[n][m] != 0) ans = bfs1_step[n][m];
	bfs2();
//	for(int i = 1;i <= n;i++){
//		for(int j  =1;j <= m;j++)
//			cout << bfs1_step[i][j] << " ";
//		cout << endl;
//	}
		
	for(auto i : h1){
		for(auto j : h2){
			//cout << i << "---" << j << endl;
			if(i != j){
				ans = min(ans,step1 + step2 + 2);	
			}else{
				//cout << i << "---" << j << endl;
				ans = min(ans,step1 + step2 + 1);
				break;
			}
		}
	}
	if(ans == INT_MAX) cout << -1;
	else cout << ans;
	return 0;
}