CH2601 电路维修

描述

Ha'nyu是来自异世界的魔女，她在漫无目的地四处漂流的时候，遇到了善良的少女Rika，从而被收留在地球上。Rika的家里有一辆飞行车。有一天飞行车的电路板突然出现了故障，导致无法启动。

电路板的整体结构是一个R行C列的网格（R,C≤500），如右图所示。每个格点都是电线的接点，每个格子都包含一个电子元件。电子元件的主要部分是一个可旋转的、连接一条对角线上的两个接点的短电缆。在旋转之后，它就可以连接另一条对角线的两个接点。电路板左上角的接点接入直流电源，右下角的接点接入飞行车的发动装置。

Ha'nyu发现因为某些元件的方向不小心发生了改变，电路板可能处于断路的状态。她准备通过计算，旋转最少数量的元件，使电源与发动装置通过若干条短缆相连。不过，电路的规模实在是太大了，Ha'nyu并不擅长编程，希望你能够帮她解决这个问题。

输入格式

输入文件包含多组测试数据。第一行包含一个整数T 表示测试数据的数目。

对于每组测试数据，第一行包含正整数R 和C，表示电路板的行数和列数。

之后R 行，每行C 个字符，字符是"/"和""中的一个，表示标准件的方向。

输出格式

对于每组测试数据，在单独的一行输出一个正整数，表示所需的缩小旋转次数。

如果无论怎样都不能使得电源和发动机之间连通，输出NO SOLUTION。

样例输入

1

3 5

\\/\\

\\///

/\\\\

样例输出

数据范围与约定

对于40% 的数据，R,C≤5。

对于100% 的数据，R,C≤500，T≤5。

样例解释

样例的输入对应于题目描述中的情况。

只需要按照下面的方式旋转标准件，就可以使得电源和发动机之间连通。

来源

杜宇飞，石家庄二中【Nescafé 5】杯NOIP模拟赛

思路

我们在格点建边，构成一个无向图。如果不用旋转就能到达，边权为0，否则为1。

然后广搜~

but 纯粹的广搜（或者SPFA?）是会炸的。。。

我得了70分。。。T了3个点。。。

我们可以考虑使用双端队列BFS

即如果边权为0，直接放到队首，如果边权为1，就和普通BFS一样放到队尾。

有时会出现这样一种情况：

最优值相同的点A，B都能更新C，A在队列中的位置在B前面。AC=1 BC=0

这样会导致最优值出现错误。所以我们还要判断能不能更新已有的点。

像上述这种情况，A更新C后，C‘会到队尾，B更新C后，C到队首，比之前的C'更快更新，C'不能再更新其他点，也就不会影响结果。

代码

#include<bits/stdc++.h>

using namespace std;

#define open(s) freopen( s".in", "r", stdin ), freopen( s".out", "w", stdout )

#define MAXN 505

int T;

int R, C;

char s[MAXN][MAXN];

int dis[MAXN][MAXN];

deque<int> Qx, Qy;

int x, y, tx, ty, t1, t2; char t;

int dir[4][2] = { 1, 1, -1, -1, 1, -1, -1, 1 };

int wh[4][2] = { 1, 1, 0, 0, 1, 0, 0, 1 };

int main(){

	scanf( "%d", &T );

	while( T-- ){

		scanf( "%d%d", &R, &C );

		for ( int i = 1; i <= R; ++i ) scanf( "%s", s[i] + 1 );

		memset( dis, 0x7f, sizeof dis );

		dis[0][0] = 0;

		Qx.push_back(0); Qy.push_back(0);

		while( !Qx.empty() ){

			x = Qx.front(); y = Qy.front(); Qx.pop_front(); Qy.pop_front();

			for ( int i = 0; i < 4; ++i ){

				tx = x + dir[i][0]; ty = y + dir[i][1];

				t1 = x + wh[i][0]; t2 = y + wh[i][1];

				t = i <= 1 ? '\\' : '/';

				if ( tx >= 0 && ty >= 0 && tx <= R && ty <= C && dis[tx][ty] > dis[x][y] + ( s[t1][t2] != t )  ){

					dis[tx][ty] = dis[x][y] + ( s[t1][t2] != t );

					if ( s[t1][t2] != t ) Qx.push_back(tx), Qy.push_back(ty);

					else Qx.push_front(tx), Qy.push_front(ty);

				}

			}

		}

		if ( dis[R][C] >= 0x3f3f3f3f ) printf( "NO SOLUTION\n" );

		else printf( "%d\n", dis[R][C] );

	}

	return 0;

}

巴特西

「CH2601」电路维修解题报告

CH2601 电路维修

描述

输入格式

输出格式

样例输入

样例输出

数据范围与约定

样例解释

来源

思路

代码

最新文章

热门文章

巴特西

「CH2601」 电路维修 解题报告

CH2601 电路维修

描述

输入格式

输出格式

样例输入

样例输出

数据范围与约定

样例解释

来源

思路

代码

最新文章

热门文章

「CH2601」电路维修解题报告