有一天飞行车的电路板突然出现了故障,导致无法启动。
电路板的整体结构是一个
行
列的网格(
),如下图所示。
?
每个格点都是电线的接点,每个格子都包含一个电子元件。...电子元件的主要部分是一个可旋转的、连接一条对角线上的两个接点的短电缆。
在旋转之后,它就可以连接另一条对角线的两个接点。
电路板左上角的接点接入直流电源,右下角的接点接入飞行车的发动装置。...第一行包含一个整数
,表示测试数据的数目。
对于每组测试数据,第一行包含正整数
和
,表示电路板的行数和列数。.../*
* 建模:以网格中节点为搜索节点
* 顺着走,则成本是 0 ,否则是 1
* 如例题中图,有 3 * 5 个格子,则有 4 * 6 个节点
* 双端队列,我们不一定把新节点放到队尾...int dx[4] = {-1, 1, 1, -1}, dy[4] = {-1, -1, 1, 1};
// 左上,右上,右下,左下 的格子
int ix[4] = {-1, 0, 0,