最近在复习搜索。
0.先说双向广搜
本蒟蒻入门是orzxgf。
考虑用一个 $9$ 位数表示矩阵， $map$ 存状态。每次从 $0$ 开始搜索。
这题很多方法都能过，这里写的是双向广搜。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>
#include <queue>
using namespace std;
int n,m[5][5],goal=123804765;
int nex[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
map <int,int> ans,vis;
queue <int> q;
void bfs()
{
if(n == goal)
{
printf("0");
return ;
}
vis[n]=1; vis[goal]=2;
ans[n]=0; ans[goal]=1;
q.push(n); q.push(goal);
int sx,sy,nx,ny,x,t;
while(!q.empty())
{
x=q.front(); q.pop();
t=x;
for(int i=3;i;i--)
for(int j=3;j;j--)
{
m[i][j]=t%10;
t/=10;
if(!m[i][j]) sx=i,sy=j;
}
for(int i=0;i<4;i++)
{
nx=sx+nex[i][0];
ny=sy+nex[i][1];
if(nx < 1 || ny < 1 || nx > 3 || ny > 3) continue ;
swap(m[sx][sy],m[nx][ny]);
t=0;
for(int j=1;j<4;j++)
for(int k=1;k<4;k++)
t=t*10+m[j][k];
if(vis[t] == vis[x])
{
swap(m[sx][sy],m[nx][ny]);
continue ;
}
if(vis[t]+vis[x] == 3)
{
printf("%d",ans[t]+ans[x]);
return ;
}
vis[t]=vis[x];
ans[t]=ans[x]+1;
q.push(t);
swap(m[sx][sy],m[nx][ny]);
}
}
return ;
}
int main()
{
// freopen("work.in","r",stdin); freopen("work.out","w",stdout);
scanf("%d",&n);
bfs();
// fclose(stdin); fclose(stdout);
return 0;
}
双向广搜还原状态非常重要，一定要在继续拓展之前还原。 我在做下一道例题的时候就被坑了。
双向广搜的两种拓展方式
- 轮流从起点和终点拓展。
- 从节点数量较少的拓展。
第二种在一般情况下会获得比较好的效率，但是实现起来没有第一种好写。
作者实在是太懒了，接下来这题他用的是第一种，感兴趣的小伙伴可以尝试用第二种写一下。
考虑状压。建议读者自己写，实在不会可以参考以下代码。
如果是调不出来可以看看是不是有符号写反，没有在 $continue$ 之前还原状态等等。
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <cstring>
#include <queue>
using namespace std;
int s,e,vis[70000],a[10][10],step[70000],nxt[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
queue <int> q;
int main()
{
// freopen("work.in","r",stdin); freopen("work.out","w",stdout);
char t;
for(int i=1;i<=16;i++) {scanf(" %c",&t); s=(s<<1)+t-'0';}
for(int i=1;i<=16;i++) {scanf(" %c",&t); e=(e<<1)+t-'0';}
if(s == e) return printf("0"),0;
vis[s]=1; vis[e]=2; step[s]=0; step[e]=0;
q.push(s); q.push(e);
int x,now;
while(!q.empty())
{
x=now=q.front(); q.pop();
for(int i=4;i;i--)
for(int j=4;j;j--) {a[i][j]=x&1; x>>=1;}
for(int i=1,nx,ny;i<=4;i++)
for(int j=1;j<=4;j++)
if(a[i][j])
for(int u=0;u<4;u++)
{
nx=i+nxt[u][0]; ny=j+nxt[u][1]; x=0;
if(nx < 1 || nx > 4 || ny < 1 || ny > 4) continue;
if(!a[nx][ny])
{
a[i][j]=0; a[nx][ny]=1;
for(int k=1;k<=4;k++)
for(int l=1;l<=4;l++) x=(x<<1)+a[k][l];
a[i][j]=1; a[nx][ny]=0;
if(vis[x]+vis[now] == 3) return printf("%d\n",step[x]+step[now]+1),0;
if(vis[x]) continue;
vis[x]=vis[now]; step[x]=step[now]+1; q.push(x);
}
}
}
// fclose(stdin); fclose(stdout);
return 0;
}
1.接下来是 $01BFS$
01BFS在甚么时候用？
你有一张图，边权只有0和1，直接BFS即可。
此时我们需要用双端队列作BFS用。
把花费0的点塞头，1的点塞尾。
这样可以保证两段性和花费小的点先遍历。
裸题。注意这里搜到不一定即最短。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <deque>
using namespace std;
int n,m,dis[520][520],sx,sy,ex,ey,nxt[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
char s[520][520];
struct node {int x,y,step;};
deque <node> q;
int main()
{
// freopen("work.in","r",stdin); freopen("work.out","w",stdout);
while(scanf("%d%d",&n,&m) == 2 && n && m)
{
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
scanf(" %c",&s[i][j]);
dis[i][j]=1e9;
}
while(!q.empty()) q.pop_back();
scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
sx++; sy++; ex++; ey++;
dis[sx][sy]=0;
q.push_back((node) {sx,sy,0});
int x,y,sum;
while(!q.empty())
{
x=q.front().x; y=q.front().y; sum=q.front().step;
if(x == ex && y == ey) break;
q.pop_front();
for(int i=0,nx,ny;i<4;i++)
{
nx=x+nxt[i][0]; ny=y+nxt[i][1];
if(nx < 1 || ny < 1 || nx > n || ny > m) continue;
if(s[x][y] == s[nx][ny] && sum < dis[nx][ny]) {dis[nx][ny]=sum; q.push_front((node) {nx,ny,sum});}
if(s[x][y] != s[nx][ny] && sum+1 < dis[nx][ny]) {dis[nx][ny]=sum+1; q.push_back((node) {nx,ny,sum+1});}
}
}
printf("%d\n",dis[ex][ey]);
}
// fclose(stdin); fclose(stdout);
return 0;
}
P4667 [BalticOI 2011 Day1]Switch the Lamp On
这题是我在上洛谷提高组图论课时候的例题。
对于每两个在同一格子同一对角线上的点，若一开始就可以走，则花费为0，否则转动花费1。
直接上01BFS。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <deque>
using namespace std;
int n,m,dis[520][520];
char c[520][520];
struct node {int x,y,step;} a;
deque <node> q;
int main()
{
// freopen("work.in","r",stdin); freopen("work.out","w",stdout);
scanf("%d%d",&n,&m);
n++; m++;
for(int i=1;i<n;i++)
for(int j=1;j<m;j++)
scanf(" %c",&c[i][j]);
q.push_back((node) {1,1,0});
int x,y,sum;
memset(dis,0x3f,sizeof(dis));
while(!q.empty())
{
a=q.front();
x=a.x; y=a.y; sum=a.step;
q.pop_front();
if(x == n && y == m) return printf("%d",sum),0;
if(x+1 <= n && y-1)
{
if(c[x][y-1] == '\\' && dis[x+1][y-1] > sum+1)
{
q.push_back((node) {x+1,y-1,a.step+1});
dis[x+1][y-1]=sum+1;
}
if(c[x][y-1] == '/' && dis[x+1][y-1] > sum)
{
q.push_front((node) {x+1,y-1,a.step});
dis[x+1][y-1]=sum;
}
}
if(x+1 <= n && y+1 <= m)
{
if(c[x][y] == '\\' && dis[x+1][y+1] > sum)
{
q.push_front((node) {x+1,y+1,a.step});
dis[x+1][y+1]=sum;
}
if(c[x][y] == '/' && dis[x+1][y+1] > sum+1)
{
q.push_back((node) {x+1,y+1,a.step+1});
dis[x+1][y+1]=sum+1;
}
}
if(x-1 && y-1)
{
if(c[x-1][y-1] == '\\' && dis[x-1][y-1] > sum)
{
q.push_front((node) {x-1,y-1,a.step});
dis[x-1][y-1]=sum;
}
if(c[x-1][y-1] == '/' && dis[x-1][y-1] > sum+1)
{
q.push_back((node) {x-1,y-1,a.step+1});
dis[x-1][y-1]=sum+1;
}
}
if(x-1 && y+1 <= m)
{
if(c[x-1][y] == '\\' && dis[x-1][y+1] > sum+1)
{
q.push_back((node) {x-1,y+1,a.step+1});
dis[x-1][y+1]=sum+1;
}
if(c[x-1][y] == '/' && dis[x-1][y+1] > sum)
{
q.push_front((node) {x-1,y+1,a.step});
dis[x-1][y+1]=sum;
}
}
}
printf("NO SOLUTION");
// fclose(stdin); fclose(stdout);
return 0;
}
练习
- SP22393 KATHTHI - KATHTHI 题解
- UVA11573 Ocean Currents
