「BZOJ2346」[Baltic 2011] Lamp

2014年8月5日3,4550

Description

2255是一个傻X，他连自己家灯不亮了都不知道。
某天TZ大神路过他家，发现了这一情况，
于是TZ开始行侠仗义了。
TZ发现是电路板的问题，
他打开了电路板，发现线路根本没有连上！！
于是他强大的脑力可以使某个格子上的线路从\变为/，
或者从/变为\。
2255不会电路（因为他什么都不会），但是他想知道TZ最少要用多少次脑力才能使他家的灯变亮。
如果无法变亮，输出“NO SOLUTION”。

n,m<=500

Sample Input

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

Sample Output

题解

对角线建边,原来有的边权为0没有的权为1，最短路

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#define inf 1000000000
#define pa pair<int,int>
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int n,m,tot,cnt;
char mp[505][505];
int mark[505][505],last[300005],dis[300005];
bool vis[300005];
struct edge{int to,next,v;}e[2000005];
void insert(int u,int v,int w)
{
	e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;
	e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=w;
}
void build()
{
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(mp[i][j]=='\\')
			{
				insert(mark[i][j],mark[i+1][j+1],0);
				insert(mark[i+1][j],mark[i][j+1],1);
			}
			else 
			{
				insert(mark[i][j],mark[i+1][j+1],1);
				insert(mark[i+1][j],mark[i][j+1],0);
			}
}
void dijkstra()
{
	priority_queue<pa,vector<pa>,greater<pa> > q;
	for(int i=1;i<=tot;i++)dis[i]=inf;
	dis[1]=0;q.push(make_pair(0,1));
	while(!q.empty())
	{
		int now=q.top().second;q.pop();
		if(vis[now])continue;vis[now]=1;
		for(int i=last[now];i;i=e[i].next)
			if(dis[now]+e[i].v<dis[e[i].to])
			{
				dis[e[i].to]=dis[now]+e[i].v;
				q.push(make_pair(dis[e[i].to],e[i].to));
			}
	}
}
int main()
{
	n=read();m=read();
	for(int i=1;i<=n;i++)
		scanf("%s",mp[i]+1);
	for(int i=1;i<=n+1;i++)
		for(int j=1;j<=m+1;j++)
			mark[i][j]=++tot;
	build();
	dijkstra();
	if(dis[tot]!=inf)printf("%d\n",dis[tot]);
	else puts("NO SOLUTION");
	return 0;
}

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<queue>

#define inf 1000000000

#define pa pair<int,int>

using namespace std;

inline int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,m,tot,cnt;

char mp[505][505];

int mark[505][505],last[300005],dis[300005];

bool vis[300005];

struct edge{int to,next,v;}e[2000005];

void insert(int u,int v,int w)

{

e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;

e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=w;

}

void build()

{

for(int i=1;i<=n;i++)

for(int j=1;j<=m;j++)

if(mp[i][j]=='\\')

{

insert(mark[i][j],mark[i+1][j+1],0);

insert(mark[i+1][j],mark[i][j+1],1);

}

else

{

insert(mark[i][j],mark[i+1][j+1],1);

insert(mark[i+1][j],mark[i][j+1],0);

}

void dijkstra()

{

priority_queue<pa,vector<pa>,greater<pa> > q;

for(int i=1;i<=tot;i++)dis[i]=inf;

dis[1]=0;q.push(make_pair(0,1));

while(!q.empty())

{

int now=q.top().second;q.pop();

if(vis[now])continue;vis[now]=1;

for(int i=last[now];i;i=e[i].next)

if(dis[now]+e[i].v<dis[e[i].to])

{

dis[e[i].to]=dis[now]+e[i].v;

q.push(make_pair(dis[e[i].to],e[i].to));

}

int main()

{

n=read();m=read();

for(int i=1;i<=n;i++)

scanf("%s",mp[i]+1);

for(int i=1;i<=n+1;i++)

for(int j=1;j<=m+1;j++)

mark[i][j]=++tot;

build();

dijkstra();

if(dis[tot]!=inf)printf("%d\n",dis[tot]);

else puts("NO SOLUTION");

return 0;

}

« 「BZOJ2304」[APIO2011] 寻路path 「BZOJ3040」最短路(road) »

hzwer.com _ Home | http://hzwer.com

「BZOJ2346」[Baltic 2011] Lamp

Description

Sample Input

Sample Output

题解

分类目录

热门文章

Myfriends

近期评论