程序设计天梯赛L3-18

题目
题意: 给定二维矩阵，起点st和终点ed。st和ed所在的直线将整个矩阵分割成两个部分，要求找到两条从st到ed的路线，一条只在矩阵的左半部分，另一条只在矩阵的右半部分，并且这两条路线的贡献要尽可能地小。贡献我感觉说有点迷，主要是举的例子把我误导了，我的理解能力不是很行。我看了题解才明白题目说的啥意思。他表达的是路线的贡献是每个点的权值之和，再加上所有斜着走的边连接的两点的权值和乘以 (根号2-1)
思路: dfs只能过一个点，还会T。可以采用分支限界法，简单来说是bfs时采用优先队列。用队列的话显然不能保证第一次搜索时是最优解，只能说明曼哈顿距离最小，但是贡献很可能不是最小。
！这里用优先队列的时候要注意出队时才将vis标记为1，我原来bfs经常入队前，换成优先队列就不能保证正确性了，类似Dij，会更新多次。记得出队vis标1，否则不标。
时间复杂度: O(nm8log(nm))
代码:

#include
using namespace std;
typedef long long ll;
const int N = 102;
int a[N][N];
int n,m,T;
int sx,sy,ex,ey;
double ans = 1e9;
double res = 1e9;
double k,b;
bool vis[N][N];
struct node{
	int x,y;
	double val;
	bool operator<(const node&rhs)const
	{
		return val > rhs.val;
	}
};
int check(int x,int y) //2:终点,1:y > kx+b.
{
	if(x==ex&&y==ey) return 2;
	if(k == 1e9)
	{
		if(x == sx) return -1;
		if(x > sx) return 1;
		return 0;
	}
	    if(y == k*x+b) return -1;
		if(y > k*x+b) return 1;
		return 0;
}
void bfs1()
{
	priority_queue<node> q;
	q.push({sx,sy,0});
	memset(vis,false,sizeof(vis));
	while(q.size())
	{
		auto tmp = q.top(); q.pop();
		int x = tmp.x; int y = tmp.y; double w = tmp.val;
		// cout<
		vis[x][y] = 1;
		if(x == ex && y == ey)
		{
		    ans = w + a[ex][ey];
			// ans = min(ans,w);
			return ;
		}
		for(int i=-1;i<=1;++i)
		{
			for(int j=-1;j<=1;++j)
			{
				if(i==0&&j==0) continue;
				int tx = x+i,ty = y+j;
				if(tx<0||ty<0||tx>=n||ty>=m) continue;
				if(vis[tx][ty]) continue;
				int flag = check(tx,ty);
				if(flag == -1 || flag == 1) continue;
				double t = a[x][y];
				if(abs(i)+abs(j)==2) t += (sqrt(2)-1)*(a[tx][ty]+a[x][y]);
				q.push({tx,ty,t+w});
			}
		}
	}
}
void bfs2()
{
	priority_queue<node> q;
	q.push({sx,sy,0});
	memset(vis,false,sizeof(vis));
	while(q.size())
	{
		auto tmp = q.top(); q.pop();
		int x = tmp.x; int y = tmp.y; double w = tmp.val;
		// cout<
		vis[x][y] = 1;
		if(x == ex && y == ey)
		{
			res = w + a[ex][ey];
			return ;
		}
		for(int i=-1;i<=1;++i)
		{
			for(int j=-1;j<=1;++j)
			{
				if(i==0&&j==0) continue;
				int tx = x+i,ty = y+j;
				if(tx<0||ty<0||tx>=n||ty>=m) continue;
				if(vis[tx][ty]) continue;
				int flag = check(tx,ty);
				if(flag == -1 || flag == 0) continue;
				double t = a[x][y];
				if(abs(i)+abs(j)==2) t += (sqrt(2)-1)*(a[tx][ty]+a[x][y]);
				q.push({tx,ty,t+w});
			}
		}
	}
}
void solve()
{
	cin>>n>>m;
	for(int i=0;i<n;++i)
    {
    	for(int j=0;j<m;++j)
    	{
    		cin>>a[i][j];
    	}
    }
    cin>>sy>>sx>>ey>>ex;
    if(sx == ex)
    {
    	k = 1e9;
    }
    else
    {
    	k = (1.0*ey-sy)/(1.0*ex-sx);
    	b = (1.0*ex*sy-1.0*sx*ey)/(1.0*ex-sx);
    }
    bfs1();
    bfs2();
    ans -= (a[sx][sy]+a[ex][ey]);
    printf("%.2lf",ans + res);
}
signed main(void)
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie();
	solve();
	return 0;
}