肝总结肝的我肝疼。
10026.电路维修
把题意转化一下，可以把每个端点看成节点，有导线相连的对角线就连一条边权为0的边，不相连的对角线就连一条边权为1的边。
然后用最短路什么的做就行了。看题解里面说最短路比较慢，再加上本来就该练习广搜，我就写了双向广搜。
struct Edge{
int next,to,w,from;
} edge[1000005];
int n,m,t,cnt,head[251005],dis[251005];
bool vis[251005];
inline void add(int u,int v,int w)
{
edge[++cnt].to=v;
edge[cnt].from=u;
edge[cnt].w=w;
edge[cnt].next=head[u];
head[u]=cnt;
}
inline int to_line(int x,int y)
{
return (x-1)*(m+1)+y;
}
inline bool bfs()
{
deque <int> q;
memset(vis,0,sizeof(vis));
q.push_front(1);
vis[1]=1;
while (!q.empty())
{
int x=edge[q.front()].from,y=edge[q.front()].to,w=edge[q.front()].w; q.pop_front();
if (vis[y]) continue;
vis[y]=1;
dis[y]=dis[x]+w;
if (y==(n+1)*(m+1)) return 1;
for (int i=head[y];i;i=edge[i].next)
{
if (vis[edge[i].to]) continue;
if (edge[i].w) q.push_back(i);
else q.push_front(i);
}
}
return 0;
}
inline void init()
{
cnt=0;
memset(dis,0,sizeof(dis));
memset(head,0,sizeof(head));
}
int main()
{
t=read();
while (t--)
{
init();
n=read(); m=read();
for (int i=1;i<=n;i++)
{
char s[505];
scanf("%s",s+1);
for (int j=1;j<=m;j++)
{
int x1=to_line(i+1,j),y1=to_line(i,j+1),x2=to_line(i,j),y2=to_line(i+1,j+1);
if (s[j]=='/')
{
add(x2,y2,1); add(y2,x2,1);
add(x1,y1,0); add(y1,x1,0);
}
else
{
add(x2,y2,0); add(y2,x2,0);
add(x1,y1,1); add(y1,x1,1);
}
}
}
if (!bfs()) printf("NO SOLUTION\n");
else printf("%d\n",dis[(n+1)*(m+1)]);
}
return 0;
}10027.魔板
这个广搜本身挺显然的，但我很傻逼。在每种操作后的结果如果被搜索过我都写了continue，然后就会跳过剩下的操作，然后我就调了半天。发现了也懒得重构了，直接用goto。
struct node{
int s[10],id;
} stat;
string ans[370005];
int goal[10],goal_id,vis[370005];
int fac[]={1,1,2,6,24,120,720,5040,40320};
inline int get_hash(int *s) //康托展开去重
{
int ans=0;
for (int i=1;i<=9;i++)
{
int sm=0;
for (int j=i+1;j<=9;j++)
if (s[j]<s[i]) sm++;
ans+=fac[8-i+1]*sm;
}
return ans;
}
inline int bfs()
{
queue <node> q;
q.push(stat);
vis[stat.id]=1;
while (!q.empty())
{
node x=q.front(); q.pop();
node bef=x;
int s[5];
memcpy(s+1,x.s+1,4*sizeof(int));
memcpy(x.s+1,x.s+5,4*sizeof(int));
memcpy(x.s+5,s+1,4*sizeof(int));
x.id=get_hash(x.s);
if (vis[x.id]) goto Case_B;
vis[x.id]=vis[bef.id]+1;
ans[x.id]=ans[bef.id]+"A";
if (x.id==goal_id) return vis[x.id];
q.push(x);
Case_B:;
x=bef;
int a=x.s[4],b=x.s[8];
for (int i=4;i>=2;i--) x.s[i]=x.s[i-1];
for (int i=8;i>=6;i--) x.s[i]=x.s[i-1];
x.s[1]=a; x.s[5]=b;
x.id=get_hash(x.s);
if (vis[x.id]) goto Case_C;
vis[x.id]=vis[bef.id]+1;
ans[x.id]=ans[bef.id]+"B";
if (x.id==goal_id) return vis[x.id];
q.push(x);
Case_C:;
x=bef;
a=x.s[2];
x.s[2]=x.s[6];
x.s[6]=x.s[7];
x.s[7]=x.s[3];
x.s[3]=a;
x.id=get_hash(x.s);
if (vis[x.id]) continue;
vis[x.id]=vis[bef.id]+1;
ans[x.id]=ans[bef.id]+"C";
if (x.id==goal_id) return vis[x.id];
q.push(x);
}
return vis[goal_id];
}
int main()
{
for (int i=1;i<=8;i++)
{
int now=(i<=4) ? i : 13-i;
goal[now]=read();
stat.s[i]=now;
}
goal_id=get_hash(goal);
stat.id=get_hash(stat.s);
printf("%d\n",bfs()-1);
cout<<ans[goal_id];
return 0;
}10028.Knight Moves
不是很懂为什么一道比一道简单。
int t,n,sx,sy,ex,ey,vis[305][305];
int fx[8]={1,2,2,1,-1,-2,-2,-1},fy[8]={2,1,-1,-2,-2,-1,1,2};
inline int bfs()
{
queue <pr> q;
q.push(mp(sx,sy));
memset(vis,0,sizeof(vis));
vis[sx][sy]=1;
while (!q.empty())
{
int x=q.front().first,y=q.front().second; q.pop();
for (int i=0;i<8;i++)
{
int tx=x+fx[i],ty=y+fy[i];
if (tx<1 || tx>n || ty<1 || ty>n || vis[tx][ty]) continue;
vis[tx][ty]=vis[x][y]+1;
if (tx==ex && ty==ey) return vis[ex][ey]-1;
q.push(mp(tx,ty));
}
}
return vis[ex][ey]-1;
}
int main()
{
t=read();
while (t--)
{
n=read(); sx=read()+1; sy=read()+1; ex=read()+1; ey=read()+1;
if (sx==ex && sy==ey) printf("0\n");
else printf("%d\n",bfs());
}
return 0;
}10029.棋盘游戏
三倍经验：洛谷P4289、loj10031（没错你没有看错就是同一章就有重题！）
这个广搜也挺裸的，搜索4个方向进行交换，转化为二进制判重即可。需要注意的是对struct里的变量用swap()好像会出锅，我因为这个调了很久。
struct node{
int s[5][5],id;
} stat,goal;
int vis[100005];
int fx[4]={0,-1,0,1},fy[4]={1,0,-1,0};
inline int get_hash(int s[5][5])
{
int now=32768,ans=0;
for (int i=1;i<=4;i++)
{
for (int j=1;j<=4;j++)
{
ans+=s[i][j]*now;
now>>=1;
}
}
return ans;
}
inline int bfs()
{
queue <node> q;
q.push(stat);
vis[stat.id]=1;
while (!q.empty())
{
node x=q.front(); q.pop();
node bef=x;
for (int i=1;i<=4;i++)
{
for (int j=1;j<=4;j++)
{
if (!x.s[i][j]) continue;
for (int k=0;k<4;k++)
{
int tx=i+fx[k],ty=j+fy[k];
if (tx<1 || tx>4 || ty<1 || ty>4) continue;
if (x.s[tx][ty]) continue;
x.s[i][j]=0; x.s[tx][ty]=1;
x.id=get_hash(x.s);
if (vis[x.id])
{
x=bef;
continue;
}
vis[x.id]=vis[bef.id]+1;
if (x.id==goal.id) return vis[x.id]-1;
q.push(x);
x=bef;
}
}
}
}
return vis[goal.id]-1;
}
int main()
{
for (int i=1;i<=4;i++)
{
char ch[5];
scanf("%s",ch+1);
for (int j=1;j<=4;j++) stat.s[i][j]=ch[j]-'0';
}
stat.id=get_hash(stat.s);
for (int i=1;i<=4;i++)
{
char ch[5];
scanf("%s",ch+1);
for (int j=1;j<=4;j++) goal.s[i][j]=ch[j]-'0';
}
goal.id=get_hash(goal.s);
printf("%d\n",bfs());
return 0;
}10030.Keyboarding
这道应该是最难的了吧。
https://llf0703.com/p/uva-1714.html
10031.移动玩具
同10029
10032.山峰和山谷
用bfs求联通块，然后判断它们是不是山峰和山谷即可。
pr ans;
int n,s[1005][1005];
bool vis[1005][1005];
int fx[8]={-1,-1,-1,0,0,1,1,1},fy[8]={1,0,-1,1,-1,1,0,-1};
inline pr bfs(int st_x,int st_y)
{
queue <pr> q;
q.push(mp(st_x,st_y));
vis[st_x][st_y]=1;
pr ans=mp(1,1);
while (!q.empty())
{
int x=q.front().first,y=q.front().second; q.pop();
for (int i=0;i<8;i++)
{
int tx=x+fx[i],ty=y+fy[i];
if (tx<1 || tx>n || ty<1 || ty>n) continue;
//if (vis[tx][ty]) continue;
if (s[x][y]==s[tx][ty] && !vis[tx][ty])
{
vis[tx][ty]=1;
q.push(mp(tx,ty));
}
else if (s[x][y]<s[tx][ty]) ans.first=0;
else if (s[x][y]>s[tx][ty]) ans.second=0;
}
}
return ans;
}
int main()
{
n=read();
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
s[i][j]=read();
for (int i=1;i<=n;i++)
{
for (int j=1;j<=n;j++)
{
if (vis[i][j]) continue;
pr now=bfs(i,j);
ans.first+=now.first;
ans.second+=now.second;
}
}
printf("%d %d",ans.first,ans.second);
return 0;
}以上。