脚本宝典收集整理的这篇文章主要介绍了ABC246E Bishop 2（bfs），脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

这题在考场上硬是没有调出来，当时百思不得其解，考场代码如下：

void bfs() {
	memset(vis, 0, sizeof(vis));
	memset(dis, inf, sizeof(dis));
	queue<pair<int, int> > que;
	que.push(make_pair(a1, b1));
	dis[a1][b1] = 0; vis[a1][b1] = 1;
	while (!que.empty()) {
		pair<int, int> cur = que.front(); que.pop();
		for (int i = 0; i < 4; i++) {
			for (int d = 1; d <= n; d++) {
				int curx = cur.First + d * dirx[i], cury = cur.second + d * diry[i];
				if (!valid(curx, cury)) break;
				if (s[curx][cury] == '#' || vis[curx][cury]) break; // 出错的地方
				dis[curx][cury] = dis[cur.first][cur.second] + 1;
				vis[curx][cury] = 1;
				que.push(make_pair(curx, cury));
			}
		}
	}
}

我当时以为，只要 ((curx, cury)) 被插入队列的话，那么就没必要在这个方向上继续扩展下去了，因为之后的位置可以通过 ((curx, cury)) 走到，因此答案一定不劣。 真是如此吗？其实并不一定。下面给出反例： 当 ((curx, cury)) 刚被加入堆中且还未被取出时，通过 ((curx, cury)) 走到的步数显然比通过 ((cur.first, cur.second)) 直接走到的步数大一。 那知道这点之后，如何修改我们的算法？ 很简单，当且仅当 (dis[cur.first][cur.second] + 1 > dis[curx][cury]) 时，我们才敢肯定 ((curx, cury)) 的决策不优于 ((cur.first, cur.second)) 的决策，才能 (break) 掉。 修改后的代码如下，即可通过此题（借用了 (spfa) 的思想）：

void bfs() {
	memset(vis, 0, sizeof(vis));
	memset(dis, inf, sizeof(dis));
	queue<pair<int, int> > que;
	que.push(make_pair(a1, b1));
	dis[a1][b1] = 0;
	while (!que.empty()) {
		pair<int, int> cur = que.front(); que.pop();
		vis[cur.first][cur.second] = 0;
		for (int i = 0; i < 4; i++) {
			for (int d = 1; d <= n; d++) {
				int curx = cur.first + d * dirx[i], cury = cur.second + d * diry[i];
				if (!valid(curx, cury) || s[curx][cury] == '#') break;
				if (dis[cur.first][cur.second] + 1 <= dis[curx][cury]) {
					dis[curx][cury] = dis[cur.first][cur.second] + 1;
					if (!vis[curx][cury]) que.push(make_pair(curx, cury)), vis[curx][cury] = 1;
				} else break; // 此时才能保证当前决策不优
			}
		}
	}
}

反思与总结：

之后进行剪枝的时候要多多考虑 corner cases，不要想当然。 这题和简单的 (bfs) 题不太一样，本题每次移动的距离可以大于 (1)，所以像我考场上无脑套用 (bfs) 模板是不可行的，需要仔细考虑剪枝的条件。 这题错的不怨，技不如人，甘拜下风，菜就多练。

脚本宝典总结

以上是脚本宝典为你收集整理的ABC246E Bishop 2（bfs）全部内容，希望文章能够帮你解决ABC246E Bishop 2（bfs）所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。