题目大意:给定一个电路板,求改变最少的板子数量使电源与灯泡联通
在对角线之间跑最短路,如果需要改变边权就是1,否则就是0
注意别忘了输出NO SOLUTION
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define M 510 using namespace std; typedef pair<int,int> abcd; int m,n; char map[M][M]; abcd heap[M*M]; int f[M][M],pos[M][M],top; void Push_Up(int t) { while(t>1&&f[heap[t].first][heap[t].second]<f[heap[t>>1].first][heap[t>>1].second]) swap(heap[t],heap[t>>1]),swap(pos[heap[t].first][heap[t].second],pos[heap[t>>1].first][heap[t>>1].second]),t>>=1; } void Insert(abcd x) { heap[++top]=x; pos[x.first][x.second]=top; Push_Up(top); } void Pop() { pos[heap[1].first][heap[1].second]=0; heap[1]=heap[top--]; if(top) pos[heap[1].first][heap[1].second]=1; int t=2; while(t<=top) { if(t<top&&f[heap[t+1].first][heap[t+1].second]<f[heap[t].first][heap[t].second]) ++t; if(f[heap[t].first][heap[t].second]<f[heap[t>>1].first][heap[t>>1].second]) swap(heap[t],heap[t>>1]),swap(pos[heap[t].first][heap[t].second],pos[heap[t>>1].first][heap[t>>1].second]),t<<=1; else break; } } const int dx[]={-1,-1,1,1}; const int dy[]={-1,1,-1,1}; const int posx[]={0,0,1,1}; const int posy[]={0,1,0,1}; const char wire[]={'\\','/','/','\\'}; void SPFA() { int i; memset(f,0x3f,sizeof f); f[0][0]=0; Insert( abcd(0,0) ); while(top) { abcd x=heap[1];Pop(); for(i=0;i<4;i++) { int xx=x.first+dx[i]; int yy=x.second+dy[i]; int posxx=x.first+posx[i]; int posyy=x.second+posy[i]; if(xx<0||yy<0||xx>m||yy>n) continue; if(f[xx][yy]>f[x.first][x.second]+(map[posxx][posyy]!=wire[i]) ) { f[xx][yy]=f[x.first][x.second]+(map[posxx][posyy]!=wire[i]); if(!pos[xx][yy]) Insert( abcd(xx,yy) ); else Push_Up(pos[xx][yy]); } } } } int main() { int i,j; cin>>m>>n; for(i=1;i<=m;i++) scanf("%s",map[i]+1); SPFA(); if(f[m][n]==0x3f3f3f3f) puts("NO SOLUTION"); else cout<<f[m][n]<<endl; }