题目背景
Elf 是来自Gliese 星球的少女，由于偶然的原因漂流到了地球上。在她无依无靠的时候，善良的运输队员Mark 和James 收留了她。Elf 很感谢Mark和James，可是一直也没能给他们帮上什么忙。
题目描述
有一天 Mark 和James 的飞行车没有办法启动了，经过检查发现原来是电路板的故障。飞行车的电路板设计很奇葩，如下图所示：
输入输出格式
输入格式：
输入文件包含多组测试数据。第一行包含一个整数T 表示测试数据的数目。
对于每组测试数据，第一行包含正整数 R 和C，表示电路板的行数和列数。
之后 R 行，每行C 个字符，字符是"/"和""中的一个，表示标准件的方向。
对于40% 的数据，R,C≤5。
对于 100% 的数据，R,C≤500，T≤5。
输出格式：
对于每组测试数据，在单独的一行输出一个正整数，表示所需的缩小旋转次数。
如果无论怎样都不能使得电源和发动机之间连通，输出 NO SOLUTION。
输入输出样例
输入样例#1：
1 3 5 \/\ \/// /\\
输出样例#1：
1
说明
样例的输入对应于题目描述中的情况。
只需要按照下面的方式旋转标准件，就可以使得电源和发动机之间连通。
题解
把一个格子拆成四个点，左上到右下和右上到左下分别连边，如果实际有边，则令边权为0，无则为1，求最短路
注意是稠密图，只能用堆优化的dijkstra
代码
一维做法：
//by 减维 #include<cstdio> #include<iostream> #include<cstring> #include<queue> #include<cmath> #include<algorithm> #define ll long long #define inf 1<<30 using namespace std; struct edge{ int to,v,ne; }e[4*501*501+5]; struct node{ int x,v; bool operator < (const node& b)const { return v>b.v; } }; int t,n,m,ecnt,head[510*510],dis[510*510]; bool vis[510*510]; void add(int x,int y,int z) { e[++ecnt].to=y; e[ecnt].v=z; e[ecnt].ne=head[x]; head[x]=ecnt; } void dij(int x) { memset(vis,0,sizeof(vis)); priority_queue<node>q; q.push((node){x,0}); dis[x]=0; while(!q.empty()) { node d=q.top(); q.pop(); if(vis[d.x])continue; vis[d.x]=1; for(int i=head[d.x];i;i=e[i].ne) { int dd=e[i].to; if(dis[dd]>dis[d.x]+e[i].v) { dis[dd]=dis[d.x]+e[i].v; if(!vis[dd])q.push((node){dd,dis[dd]}); } } } } int main() { scanf("%d",&t); while(t--) { ecnt=0; memset(head,0,sizeof(head)); memset(e,0,sizeof(e)); scanf("%d%d",&n,&m); for(int i=1;i<=n;++i) { char a[510]; scanf("%s",a+1); for(int j=1;j<=m;++j) { int x1=(i-1)*(m+1)+j,x2=(i-1)*(m+1)+j+1,x3=i*(m+1)+j,x4=i*(m+1)+j+1; if(a[j]=='/') { add(x1,x4,1),add(x4,x1,1); add(x2,x3,0),add(x3,x2,0); }else{ add(x1,x4,0),add(x4,x1,0); add(x2,x3,1),add(x3,x2,1); } } } for(int i=1;i<=(n+1)*(m+1);++i)dis[i]=inf; dij(1); if(dis[(n+1)*(m+1)]==inf)printf("NO SOLUTION "); else printf("%d ",dis[(n+1)*(m+1)]); } }
二维做法：
//by 减维 #include<cstdio> #include<iostream> #include<cstring> #include<queue> #include<cmath> #include<algorithm> #define ll long long using namespace std; struct edge{ int tx,ty,v,ne; }e[4*501*501+5]; struct node{ int x,y,v; bool operator < (const node& b)const { return v>b.v; } }; int t,n,m,ecnt,head[505][505],dis[505][505]; char a[510]; bool vis[505][505]; void add(int xa,int xb,int ya,int yb,int v) { e[++ecnt].tx=ya; e[ecnt].ty=yb; e[ecnt].v=v; e[ecnt].ne=head[xa][xb]; head[xa][xb]=ecnt; } void dij(int xa,int xb) { memset(dis,0x7f,sizeof(dis)); memset(vis,0,sizeof(vis)); priority_queue<node> q; dis[xa][xb]=0; q.push((node){xa,xb,0}); while(!q.empty()) { node d=q.top(); q.pop(); if(vis[d.x][d.y])continue; vis[d.x][d.y]=1; for(int i=head[d.x][d.y];i;i=e[i].ne) { int dx=e[i].tx,dy=e[i].ty; if(dis[dx][dy]>dis[d.x][d.y]+e[i].v) { dis[dx][dy]=dis[d.x][d.y]+e[i].v; if(!vis[dx][dy])q.push((node){dx,dy,dis[dx][dy]}); } } } } int main() { scanf("%d",&t); while(t--) { ecnt=0; memset(head,0,sizeof(head)); memset(e,0,sizeof(e)); scanf("%d%d",&n,&m); for(int i=1;i<=n;++i) { scanf("%s",a+1); for(int j=1;j<=m;++j) { if(a[j]=='/')add(i,j+1,i+1,j,0),add(i+1,j,i,j+1,0),add(i,j,i+1,j+1,1),add(i+1,j+1,i,j,1); else add(i,j+1,i+1,j,1),add(i+1,j,i,j+1,1),add(i,j,i+1,j+1,0),add(i+1,j+1,i,j,0); } } dij(1,1); if(dis[n+1][m+1]!=dis[0][0])printf("%d ",dis[n+1][m+1]); else printf("NO SOLUTION "); } }