Loading... # 题目描述 达达是来自异世界的魔女，她在漫无目的地四处漂流的时候，遇到了善良的少女翰翰，从而被收留在地球上。 翰翰的家里有一辆飞行车。 有一天飞行车的电路板突然出现了故障，导致无法启动。 电路板的整体结构是一个 $R$ 行 $C$ 列的网格（$R,C \leq 500$），如下图所示。  每个格点都是电线的接点，每个格子都包含一个电子元件。 电子元件的主要部分是一个可旋转的、连接一条对角线上的两个接点的短电缆。 在旋转之后，它就可以连接另一条对角线的两个接点。 电路板左上角的接点接入直流电源，右下角的接点接入飞行车的发动装置。 达达发现因为某些元件的方向不小心发生了改变，电路板可能处于断路的状态。 她准备通过计算，旋转最少数量的元件，使电源与发动装置通过若干条短缆相连。 不过，电路的规模实在是太大了，达达并不擅长编程，希望你能够帮她解决这个问题。 **注意**：只能走斜向的线段，水平和竖直线段不能走。 # 输入 输入文件包含多组测试数据。 第一行包含一个整数 $T$，表示测试数据的数目。 对于每组测试数据，第一行包含正整数 $R$ 和 $C$，表示电路板的行数和列数。 之后 $R$ 行，每行 $C$ 个字符，字符是`"/"`和`"\"`中的一个，表示标准件的方向。 # 输出 对于每组测试数据，在单独的一行输出一个正整数，表示所需的最小旋转次数。 如果无论怎样都不能使得电源和发动机之间连通，输出 `NO SOLUTION`。 # 解题思路 首先先对本体的模型进行建模处理， 发现可以将题目简化为一个图模型。其中， 每个顶点和其斜方向的四个顶点有边连接， 边权为0或1, 取决于是否需要翻转元件。 对于这样的图模型， 可以考虑使用bfs计算。 首先尝试普通的bfs算法， 发现普通的bfs算法无法解决这个问题， 因为他的边权并非全为同一个常数， 因此无法满足队列的两段性和单调性的原则。 因此考虑使用双端队列： - 已知边权只有两种：0或1 - 为了确保队列的两段性和单调性，将由0边权转移得到的边插入到队头， 将由1边权转移到的边添加到队尾，如此便可以保持队列的两段性和单调性。 - 由于图的复杂性，每一个节点都可能被多个节点遍历到，由于边权不唯一， 应该**允许每个节点多次入队**， 因此入队的时候无法保证为最小值。但由于队列的单调性， 出队时一定为该节点距离的最小值。 # AC代码 ```cpp #include <cstdio> #include <cstdlib> #include <iostream> #include <vector> #include <cstring> #include <deque> #define endl '\n' using namespace std; const int N = 510; typedef pair<int, int> PII; int n, m; char s[N][N]; int t; char correct[] = {'\\', '/', '\\', '/'}; int dx[] = {-1, -1, 1, 1}, dy[] = {-1, 1, 1, -1}; int cx[] = {-1, -1, 0, 0}, cy[] = {-1 ,0, 0, -1}; int dist[N][N]; void bfs() { deque<PII> q; q.push_back({1, 1}); dist[1][1] = 0; while(q.size()) { auto t = q.front(); q.pop_front(); int x = t.first, y = t.second; // if(x == n + 1 && y == m + 1) return dist[n + 1][m + 1]; for(int i = 0; i < 4; i ++) { int nx = x + dx[i], ny = y + dy[i]; if(nx < 1 || nx > n + 1 || ny < 1 || ny > m + 1) continue; int sx = x + cx[i], sy = y + cy[i]; int value; if(correct[i] == s[sx][sy]) value = 0; else value = 1; int d = dist[x][y] + value; if(d < dist[nx][ny]) { dist[nx][ny] = d; if(value == 1) q.push_back({nx, ny}); else q.push_front({nx, ny}); } } } // return -1; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> t; while(t --) { cin >> n >> m; for(int i = 1; i <= n; i ++) cin >> s[i] + 1; memset(dist, 0x3f, sizeof dist); bfs(); if(dist[n + 1][m + 1] == 0x3f3f3f3f) cout << "NO SOLUTION" << endl; else cout << dist[n + 1][m + 1] << endl; } return 0; } /* 入队不一定是最短距离， 出队的时候才是最短的距离 */ ``` 最后修改：2025 年 02 月 26 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏