2346: [Baltic 2011]Lamp
Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 428 Solved: 179
[Submit][Status][Discuss]
Description
2255是一个傻X，他连自己家灯不亮了都不知道。
某天TZ大神路过他家，发现了这一情况，
于是TZ开始行侠仗义了。
TZ发现是电路板的问题，
他打开了电路板，发现线路根本没有连上！！
于是他强大的脑力可以使某个格子上的线路从\变为/，
或者从/变为\。
2255不会电路（因为他什么都不会），但是他想知道TZ最少要用多少次脑力才能使他家的灯变亮。
如果无法变亮，输出“NO SOLUTION”。
n,m<=500
Input
Output
Sample Input
3 5
\\/\\
\\///
/\\\\
\\/\\
\\///
/\\\\
Sample Output
1
HINT
Source
题解：
dijkstra+堆优化.
这道题可以很容易的想到。当格子为'\',把从左上到右下加边，边权为0，右上到左下加边，边权为1。格子为'/'同理。
#include<bits/stdc++.h>
using namespace std;
#define MAXN 251011
#define INF 1e9
struct node
{
int begin,end,value,next;
}edge[];
int Head[MAXN],cnt,N,m,dis[MAXN],Heap[MAXN],SIZE,pos[MAXN];
int xy(int x,int y){return (x-)*(m+)+y;}
void addedge(int bb,int ee,int vv)
{
edge[++cnt].begin=bb;edge[cnt].end=ee;edge[cnt].value=vv;edge[cnt].next=Head[bb];Head[bb]=cnt;
}
void addedge1(int bb,int ee,int vv)
{
addedge(bb,ee,vv);addedge(ee,bb,vv);
}
void Push1(int k)
{
int now=k,root;
while(now>)
{
root=now/;
if(dis[Heap[root]]<=dis[Heap[now]])return;
swap(Heap[root],Heap[now]);
swap(pos[Heap[root]],pos[Heap[now]]);
now=root;
}
}
void Insert(int k)
{
Heap[++SIZE]=k;pos[k]=SIZE;Push1(SIZE);
}
void Pop1(int k)
{
int now,root=k;
pos[Heap[k]]=;Heap[k]=Heap[SIZE--];if(SIZE>)pos[Heap[k]]=k;
while(root<=SIZE/)
{
now=root*;
if(now<SIZE&&dis[Heap[now+]]<dis[Heap[now]])now++;
if(dis[Heap[root]]<=dis[Heap[now]])return;
swap(Heap[root],Heap[now]);
swap(pos[Heap[root]],pos[Heap[now]]);
root=now;
}
}
int dijkstra(int start)
{
int i,u,v;
for(i=;i<=N;i++)dis[i]=INF;dis[start]=;
for(i=;i<=N;i++)Insert(i);
while(SIZE>)
{
u=Heap[];Pop1(pos[u]);
for(i=Head[u];i!=-;i=edge[i].next)
{
v=edge[i].end;
if(dis[v]>dis[u]+edge[i].value){dis[v]=dis[u]+edge[i].value;Push1(pos[v]);}
}
}
return dis[N];
}
int main()
{
int n,i,j,ans;
char a;
scanf("%d %d",&n,&m);
N=(n+)*(m+);
memset(Head,-,sizeof(Head));cnt=;
for(i=;i<=n;i++)
{
scanf("\n");
for(j=;j<=m;j++)
{
scanf("%c",&a);
if(a=='/')
{
addedge1(xy(i,j),xy(i+,j+),);
addedge1(xy(i+,j),xy(i,j+),);
//addedge1(xy(i,j),xy(i+1,j+1),0);
//addedge1(xy(i+1,j),xy(i,j+1),1);
}
else
{
//addedge1(xy(i,j),xy(i+1,j+1),1);
//addedge1(xy(i+1,j),xy(i,j+1),0);
addedge1(xy(i,j),xy(i+,j+),);
addedge1(xy(i+,j),xy(i,j+),);
}
}
}
ans=dijkstra();
if(ans==INF)printf("NO SOLUTION");
else printf("%d",ans);
fclose(stdin);
fclose(stdout);
return ;
}