BZOJ2346: [Baltic 2011]Lamp

题解:

显然利用最短路求解就行了.

代码:

#include<cstdio>
#include<cctype>
#include<climits>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

#define inf 0x3f3f3f3f
#define mp make_pair
typedef pair<int,int> pii;
struct SegmentTree{
	pii s[524288];
	int M;
	inline void init(int _siz){
		for(M=1;M<(_siz+2);M<<=1);
		for(int i=1;i<(M<<1);++i)
			s[i]=mp(inf,0);
		for(int i=1;i<=_siz;++i)
			s[M+i].second=i;
	}
	inline void upd(int x,int v){
		for(s[x+=M].first=v,x>>=1;x;x>>=1)
			s[x]=min(s[x<<1],s[x<<1^1]);
	}
}Seg;

#define N 500010
#define M 2000010
int head[N],next[M],end[M],len[M];
inline void addedge(int a,int b,int c){
	static int q=1;
	end[q]=b;
	next[q]=head[a];
	head[a]=q;
	len[q++]=c;
}
inline void make(int a,int b,int c){
	addedge(a,b,c);
	addedge(b,a,c);
}


char s[510];
int ch[510][510];
int dis[N];
int main(){
#ifndef ONLINE_JUDGE
	freopen("tt.in","r",stdin);
#endif
	int n,m;
	scanf("%d%d",&n,&m);
	int i,j,id=0;
	for(i=0;i<=n;++i)
		for(j=0;j<=m;++j)
			ch[i][j]=++id;
	for(i=0;i<n;++i){
		scanf("%s",s);
		for(j=0;j<m;++j){
			if(s[j]=='\\'){
				make(ch[i][j],ch[i+1][j+1],0);
				make(ch[i+1][j],ch[i][j+1],1);
			}
			else{
				make(ch[i+1][j],ch[i][j+1],0);
				make(ch[i][j],ch[i+1][j+1],1);
			}
		}
	}
	Seg.init(id);
	Seg.upd(1,0);
	int x;
	memset(dis,0x3f,sizeof dis);
	dis[1]=0;
	for(i=1;i<=id;++i){
		x=Seg.s[1].second;
		for(j=head[x];j;j=next[j])
			if(dis[end[j]]>dis[x]+len[j])
				Seg.upd(end[j],dis[end[j]]=dis[x]+len[j]);
		Seg.upd(x,inf);
	}
	if(dis[ch[n][m]]==inf)
		cout<<"NO SOLUTION"<<endl;
	else
		cout<<dis[ch[n][m]]<<endl;
	return 0;
}