求助!RE
查看原帖
求助!RE
79543
一大楼主2021/7/17 19:48

#include<bits/stdc++.h>
using namespace std;
int n,m;
char c[501][501];
struct edge{
	int f,t,s;
}a[501*501];
int head[501*501],cnt;
void uni(int x,int y,int z){	
	a[++cnt].t =y;
	a[cnt].f =head[x];
	a[cnt].s =z;
	head[x] =cnt;
}
void add(int f,int t,int s){
	uni(f,t,s);
//	cout<<f<<" "<<t<<" "<<s<<endl;
	uni(t,f,s);
}
inline int dist[1000001];
inline int vis[1000000];
priority_queue<pair<int,int> > q;
inline void djs(int x){
	for(int i=1;i<=(n+1)*(m+1);i++) dist[i]=0x7fffffff;
	memset(vis,0,sizeof(vis));
	dist[x]=0;
	q.push(make_pair(0,x));
	while(!q.empty()){
		int t=q.top().second;
		q.pop();
		if(vis[t]) continue;
		vis[t]=1;
		for(int i=head[t];i;i=a[i].f ){
			if(a[i].s +dist[t]<dist[a[i].t ]){
				dist[a[i].t ]=a[i].s+dist[t];
				q.push(make_pair(-dist[a[i].t ],a[i].t ));
			}
		}
		
	}

}
int main(){
	for(int i=1;i<=500*500;i++) a[i].s=0x7fffffff;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>c[i][j];
			if(c[i][j]=='/'){	//(i-1)(m+1)+j,(i-1)(m+1)+j+1
								//(i)(m+1)+j  ,(i)(m+1)+j+1
				add((i-1)*(m+1)+j,(i)*(m+1)+j+1,1);
				add((i-1)*(m+1)+j+1,(i)*(m+1)+j,0);
			}
			if(c[i][j]== '\\'){
				add((i-1)*(m+1)+j,(i)*(m+1)+j+1,0);
				add((i-1)*(m+1)+j+1,(i)*(m+1)+j,1);
			}
		}
	}
	djs(1);
//	cout<<dist[(n+1)*(m+1)];
	if(dist[(n+1)*(m+1)]==0x7fffffff) cout<<"NO SOLUTION";
	else  cout<<dist[(n+1)*(m+1)];
}





不知道为什么RE一堆点

2021/7/17 19:48
加载中...