|
|
///*
|
|
|
// * 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;
|
|
|
//}
|
