# 题目

image-20210319205815067

# 题意

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

# 思路

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

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

# CODE

#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;
}
更新于

请我喝[茶]~( ̄▽ ̄)~*

PocketCat 微信支付

微信支付

PocketCat 支付宝

支付宝