开发软件网站建设,移动网站 pc网站的区别,有没有专门做渔具的网站,赣州市微语网络科技有限公司题目链接
电路维修
题目描述
达达是来自异世界的魔女#xff0c;她在漫无目的地四处漂流的时候#xff0c;遇到了善良的少女翰翰#xff0c;从而被收留在地球上。翰翰的家里有一辆飞行车。有一天飞行车的电路板突然出现了故障#xff0c;导致无法启动。
电路板的整体结…题目链接
电路维修
题目描述
达达是来自异世界的魔女她在漫无目的地四处漂流的时候遇到了善良的少女翰翰从而被收留在地球上。翰翰的家里有一辆飞行车。有一天飞行车的电路板突然出现了故障导致无法启动。
电路板的整体结构是一个 R R R行 C C C列的网格 R , C ≤ 500 R,C≤500 R,C≤500如下图所示 每个格点都是电线的接点每个格子都包含一个电子元件。电子元件的主要部分是一个可旋转的、连接一条对角线上的两个接点的短电缆。在旋转之后它就可以连接另一条对角线的两个接点。电路板左上角的接点接入直流电源右下角的接点接入飞行车的发动装置。
达达发现因为某些元件的方向不小心发生了改变电路板可能处于断路的状态。她准备通过计算旋转最少数量的元件使电源与发动装置通过若干条短缆相连。不过电路的规模实在是太大了达达并不擅长编程希望你能够帮她解决这个问题。
注意只能走斜向的线段水平和竖直线段不能走。
输入描述
输入文件包含多组测试数据。
第一行包含一个整数 T T T表示测试数据的数目。对于每组测试数据第一行包含正整数 R R R和 C C C表示电路板的行数和列数。
之后 R R R行每行 C C C个字符字符是/和\中的一个表示标准件的方向。
输出描述
对于每组测试数据在单独的一行输出一个正整数表示所需的缩小旋转次数。 如果无论怎样都不能使得电源和发动机之间连通输出NO SOLUTION。
样例输入
1
3 5
\\/\\
\\///
/\\\\样例输出
1算法思想
根据题目描述每个格子都包含一个电子元件主要部分是一个可旋转的、连接一条对角线上的两个接点的短电缆如下图所示。 旋转一个电子元件的代价为 1 1 1问最少旋转几个元件使起点与终点通过若干条短缆相连。
连通性
由于只能走斜向的线段水平和竖直线段不能走所以选择左上角的接点作为起点只能连接如下图左绿色的接点二下图右红色的接点是无法连通的。 通过分析发现如果将起点设为左上角那么能够连接的点绿色其行列值的和为偶数。因此是否使得电源和发动机之间连通需要判断 ( n m ) (nm) (nm)是否为偶数。
最小代价
如果电子元件的最初状态为下图所示那么从 A − B A-B A−B的代价为 0 0 0不需要旋转而从 C − D C-D C−D的代价为 1 1 1需要旋转 1 1 1次。 因此求旋转最少数量的元件使电源与发动装置通过若干条短缆相连可以转换为求从起点到终点当连接的两点之间代价为 0 0 0或 1 1 1时的最短路。
双端队列广搜
对于只包含边权 0 0 0和 1 1 1的最短路问题可以使用双端队列广搜求解。与普通的BFS不同的是
如果扩展到的新节点边权为 0 0 0时需要把新节点插入队列的头部。
这样处理满足BFS的两个性质
两段性队列中同时存在的所有点到起点的距离差值最多是1。单调性队列分成两段前面一定是小的
因此可以使用BFS求最短路。
代码实现
#include iostream
#include cstring
#include queue
using namespace std;typedef pairint, int PII;
const int N 505;
char g[N][N];
int n, m, st[N][N], dis[N][N];//元件的偏移值:左上右上右下左下
int dx[4] {-1, -1, 1, 1}, dy[4] {-1, 1, 1, -1};
//连接元件的电缆方向在字符数组位置的偏移值:左上右上右下左下
int ix[4] {-1, -1, 0, 0}, iy[4] {-1, 0, 0, -1};
//不需要旋转的连接方向左上右上右下左下
char c[] \\/\\/; //\/\/
int bfs()
{memset(st, 0, sizeof st);memset(dis, 0x3f, sizeof dis);dequePII q;dis[0][0] 0; q.push_back({0, 0});while(q.size()){PII t q.front(); q.pop_front(); //从队头出队int x t.first, y t.second;if(st[x][y]) continue;st[x][y] true;for(int i 0; i 4; i ){//扩展到的元件左上角的行列值int a x dx[i], b y dy[i]; if(a 0 || a n || b 0 || b m) continue;int ai x ix[i], bi y iy[i];//元件方向在数组中的位置int w g[ai][bi] ! c[i]; //如果不是正确的连接方向需要旋转边权为1if(dis[a][b] dis[x][y] w){dis[a][b] dis[x][y] w;if(w 1) q.push_back({a, b}); //边权为1加入队尾else q.push_front({a, b}); //边权为0加入队头}}}return dis[n][m];
}
int main()
{int T;cin T;while(T --){cin n m;for(int i 0; i n; i ) cin g[i];if(n m 1) {puts(NO SOLUTION);continue;}int t bfs();if(t 0x3f3f3f3f) puts(NO SOLUTION);else cout t \n;}
}
