///*
// * map01.cpp
// *
// *  Created on: May 7, 2024
// *      Author: 28032
//*/
//
////1.分为两种情况，可以是不依靠通道到达终点；也可以是通过通道到达终点
////结果取其中较小的一个
////2.先计算第一种情况，第二种情况可以在第一种情况上加工：找到一个通道到达起点的代价最小，再找到一个通道到达终点的代价最小
////为什么不找三及以上个通道：假设找三个通道将三个通道连成一个三角形，为什么不直达而是多到一个站呢，因而只取两个通道
////3.计算第一种情况，要考虑到起点与终点不能直接到达的情况，所以要分别从起点和终点开始BFS求到达每个格子的代价
////不能到达的显示一开始初始化的最大值
//#include <iostream>
//#include <queue>
//using namespace std;
//
//#define maxMAP 2010
//
//int MAP[maxMAP][maxMAP];
//
//long long S[maxMAP][maxMAP],
//		  E[maxMAP][maxMAP];
//int m,n,w;
//
//int x[] = {1,0,-1,0};
//int y[] = {0,1,0,-1};
//
//void BFS(long long t[maxMAP][maxMAP],int xx,int yy)
//{
//	t[yy][xx] = 0;
//	queue<pair<int,int> > coordinates;
//
//	coordinates.push({xx,yy});
//
//	while(!coordinates.empty())
//	{
//		pair<int,int> co = coordinates.front();
//		coordinates.pop();
//
//		for(int i = 0;i < 4;i++)
//		{
//			int x_next = co.first + x[i];
//			int y_next = co.second + y[i];
//
//			if(MAP[y_next][x_next] != -1 && t[y_next][x_next] == 1e18 && 1 <= x_next && x_next <=m && 1 <= y_next && y_next <= n)
//			{
//				t[y_next][x_next] = t[co.second][co.first] + w;
//				coordinates.push({x_next,y_next});
//			}
//		}
//	}
//
//}
//int main()
//{
//	cin>>n>>m>>w;
//
//	for(int i = 1;i <= n;i++)
//		for(int j = 1;j <= m;j++)
//			cin>>MAP[i][j],S[i][j] = 1e18,E[i][j] = 1e18;
//
//	BFS(S,1,1);
//	BFS(E,m,n);
//	long long ans = S[n][m];
//
//	long long s_to_turnal = 1e18,
//			  e_to_turnal = 1e18;
//
//	for(int i = 1;i <=n;i++)
//		for(int j = 1;j <= m;j++)
//			if(MAP[i][j]>=1)
//			{
//				s_to_turnal = min(s_to_turnal,S[i][j]+MAP[i][j]);
//				e_to_turnal = min(e_to_turnal,E[i][j]+MAP[i][j]);
//			}
//
//	ans = min(ans,s_to_turnal + e_to_turnal);
//
//	if(ans == 1e18)
//		cout<<-1<<endl;
//	else
//		cout<<ans<<endl;
//
//
//
//	return 0;
//}