题目

image-20210319205815067

题意

如图所示，旋转最少的电线使得左面的电源和发光器相连、

思路

考虑把所有电线已经相连的点设为边权为0，没有连接的，比如电线是主对角线，副对角线上的两个点就应该设为边权为1，最后跑一个从左上角到右下角的最短路径，将每一个点映射到一维数组中。

dijstla当然可以做，但是双端队列更高，因为这个图中只有边权为0和1的点，可以把优先队列的log(n)省掉，当遇到边权为0的点时就把点直接添加到队头，遇到边权为1的点放到队尾，并且判断能否更新当前点离起点的距离。

CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <bits/stdc++.h>
#define debug freopen("in.txt","r",stdin); freopen("out.txt","w",stdout)
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int MAXN=1e6+100;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;
const int SUB=-0x3f3f3f3f;
const double eps=1e-4;
const double E=exp(1);
const double pi=acos(-1);
struct node{
	int to,next,w;
}e[MAXN];
struct point{
	int x,y;
};
int head[MAXN],dis[MAXN];
int t,n,tot,m;
bool vis[MAXN];
void add(int u,int v,int w){
	e[tot]={v,head[u],w};
	head[u]=tot++;
}
int get(int x,int y){
	return (x-1)*(m+1)+y;
} 
struct Node{
	int u,d;
	bool operator<(const Node &o) const{
		return d>o.d;
	}
};
//priority_queue<Node> pq;
//void dij(int s){
//	memset(vis,0,sizeof vis);
//	memset(dis,0x3f,sizeof(dis));
//	pq.push({s,0});
//	dis[s]=0;
//	while(!pq.empty()){
//		Node now=pq.top();
//		pq.pop();
//		if(vis[now.u]) continue;
////		cout<<now.u<<'\n';
//		vis[now.u]=1;
//		for(int i=head[now.u];~i;i=e[i].next){
//			int v=e[i].to,w=e[i].w;
//			if(dis[v]>dis[now.u]+w){
//				dis[v]=dis[now.u]+w;
//				pq.push({v,dis[v]});
//			}
//		}
//	}
//}
deque<int> dq;
void bfs(int s){
	memset(dis,0x3f,sizeof dis);
	memset(vis,0,sizeof vis);
	dq.push_back(s);
	dis[s]=0;
	while(!dq.empty()){
		int fr=dq.front();
		dq.pop_front();
		if(vis[fr]) continue;
		vis[fr]=1;
		for(int i=head[fr];~i;i=e[i].next){
			int v=e[i].to,w=e[i].w;
			if(w==0){
				dis[v]=dis[fr];
				dq.push_front(v);
			}
			else{
				if(dis[v]>dis[fr]+w){
					dis[v]=dis[fr]+w;
					dq.push_back(v);
				}
			}
		}
	}
}
int main(){
	ios;
	cin>>t;
	while(t--){
		tot=0;
		memset(head,-1,sizeof head);
		cin>>n>>m;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				char ch;
				cin>>ch;
				if(ch=='\\'){
					add(get(i,j),get(i+1,j+1),0);
					add(get(i+1,j+1),get(i,j),0);
					add(get(i,j+1),get(i+1,j),1);
					add(get(i+1,j),get(i,j+1),1);
				}
				else{
					add(get(i,j+1),get(i+1,j),0);
					add(get(i+1,j),get(i,j+1),0);
					add(get(i,j),get(i+1,j+1),1);
					add(get(i+1,j+1),get(i,j),1);
				}
			}
		}
		bfs(get(1,1));
		if(dis[get(n+1,m+1)]==INF) cout<<"NO SOLUTION\n";
		else cout<<dis[get(n+1,m+1)]<<'\n';
	}
	return 0;
}