CH2601/洛谷P2243 电路维修（双端队列BFS）

墨蓝 2021-11-17 03:58 314阅读 0赞

## 题意： ##

**描述**

Ha'nyu是来自异世界的魔女，她在漫无目的地四处漂流的时候，遇到了善良的少女Rika，从而被收留在地球上。Rika的家里有一辆飞行车。有一天飞行车的电路板突然出现了故障，导致无法启动。  
电路板的整体结构是一个R行C列的网格（R,C≤500），如右图所示。每个格点都是电线的接点，每个格子都包含一个电子元件。电子元件的主要部分是一个可旋转的、连接一条对角线上的两个接点的短电缆。在旋转之后，它就可以连接另一条对角线的两个接点。电路板左上角的接点接入直流电源，右下角的接点接入飞行车的发动装置。

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

**输入格式**

输入文件包含多组测试数据。第一行包含一个整数 T 表示测试数据的数目。  
对于每组测试数据，第一行包含正整数 R 和 C，表示电路板的行数和列数。  
之后 R 行，每行 C 个字符，字符是"/"和"\\"中的一个，表示标准件的方向。

**输出格式**

对于每组测试数据，在单独的一行输出一个正整数，表示所需的缩小旋转次数。  
如果无论怎样都不能使得电源和发动机之间连通，输出NO SOLUTION。

**样例输入**

1
    3 5
    \\/\\
    \\///
    /\\\\

**样例输出**

**数据范围与约定**

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

## 分析：双端队列BFS模板，详见《算法竞赛进阶指南》P120。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    const int N = 506;
    int r, c, d[N][N];
    bool v[N][N];
    char s[N][N];
    vector<pair<pair<int, int>, int> > p[N][N];
    deque<pair<int, int> > q;
    
    void add(int x1, int y1, int x2, int y2, int z) {
    	p[x1][y1].push_back(make_pair(make_pair(x2, y2), z));
    }
    
    void solve() {
    	cin >> r >> c;
    	for (int i = 1; i <= r; i++) cin >> (s[i] + 1);
    	if ((r & 1) != (c & 1)) cout << "NO SOLUTION" << endl;
    	for (int i = 0; i <= r; i++)
    		for (int j = 0; j <= c; j++)
    			p[i][j].clear();
    	for (int i = 1; i <= r; i++)
    		for (int j = 1; j <= c; j++)
    			if (s[i][j] == '/') {
    				add(i - 1, j - 1, i, j, 1);
    				add(i, j, i - 1, j - 1, 1);
    				add(i, j - 1, i - 1, j, 0);
    				add(i - 1, j, i, j - 1, 0);
    			} else {
    				add(i - 1, j - 1, i, j, 0);
    				add(i, j, i - 1, j - 1, 0);
    				add(i, j - 1, i - 1, j, 1);
    				add(i - 1, j, i, j - 1, 1);
    			}
    	memset(d, 0x3f, sizeof(d));
    	d[0][0] = 0;
    	memset(v, 0, sizeof(v));
    	q.clear();
    	q.push_back(make_pair(0, 0));
    	while (q.size()) {
    		int x = q.front().first, y = q.front().second;
    		q.pop_front();
    		v[x][y] = 1;
    		if (x == r && y == c) {
    			cout << d[r][c] << endl;
    			return;
    		}
    		for (unsigned int i = 0; i < p[x][y].size(); i++) {
    			int nx = p[x][y][i].first.first;
    			int ny = p[x][y][i].first.second;
    			int nz = p[x][y][i].second;
    			if (v[nx][ny]) continue;
    			if (nz) {
    				if (d[nx][ny] > d[x][y] + 1) {
    					d[nx][ny] = d[x][y] + 1;
    					q.push_back(make_pair(nx, ny));
    				}
    			} else {
    				if (d[nx][ny] > d[x][y]) {
    					q.push_front(make_pair(nx, ny));
    					d[nx][ny] = d[x][y];
    				}
    			}
    		}
    	}
    }
    
    int main() {
    	int t;
    	cin >> t;
    	while (t--) solve();
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RpYW53ZWkwODIy_size_16_color_FFFFFF_t_70]: /images/20211116/ddd3fc5aa012490fa741f2b2ba7108f7.png