程序设计天梯赛L3-18 (什么分支限界bfs)

题目 题意: 给定二维矩阵，起点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 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 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