0-1BFS 学习记录

时间：2021-07-11 15:44:18

0-1BFS用来解决：边权值为0或1，或者能够转化为这种边权值的最短路问题，时间复杂度为O(E+V).

0-1BFS,从队列front中去除点u，遍历u的所有边，如果当前边可以进行relax操作，则relax，然后判断level，若level相同，放到队列的front，否则，放到back，队列采用双端队列deque。

实际上跟最短路挺像。

另外：由于松弛操作的存在，0-1bfs可以去掉vis数组，而且速度会更快。

SPOJKATHTHI KATHTHI

题目链接

题解，赤裸裸的0-1bfs

#include<bits/stdc++.h>
#define MEM(a,x) memset(a,x,sizeof(a));
#define MEMINF(a) memset(a,0x3f,sizeof(a));
using namespace std;
typedef long long LL;
const int MAXN=1e3+10;
const int INF=0x3f3f3f3f;
const int MOD=1000000007;
int dp[MAXN][MAXN];
char mp[MAXN][MAXN];
bool vis[MAXN][MAXN];
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int n,m;
struct Node {
  int x;
  int y;
  int step;
}now,nex;

deque<Node>q;
void bfs() {
  dp[0][0]=0;
  now.x=0,now.y=0;
  now.step=0;
  q.push_front(now);
  while(!q.empty()) {
    now=q.front();
    q.pop_front();
    for (int i=0; i<4; ++i) {
      nex=now;
      nex.x+=dx[i];
      nex.y+=dy[i];
      if (nex.x<0||nex.x>=n||nex.y<0||nex.y>=m)continue;
      nex.step=1;
      if (mp[now.x][now.y]==mp[nex.x][nex.y]) nex.step=0;
      if (dp[now.x][now.y]+nex.step<dp[nex.x][nex.y]) {
        dp[nex.x][nex.y]=dp[now.x][now.y]+nex.step;
        nex.step==1? q.push_back(nex):q.push_front(nex);
      }
    }
  }
}


int main() {
  int T;
  cin>>T;
  while(T--) {
    scanf("%d %d",&n,&m);
    for (int i=0; i<n; ++i) scanf("%s",mp[i]);
    MEMINF(dp);
    MEM(vis,false);
    bfs();
    printf("%d\n",dp[n-1][m-1]);

  }
}

UVA11573  Ocean Currents

题目

题意：给你一张图，0-7代表不同的海浪方向，你从一点可像周围8个方向移动，逆流耗费1点体力，顺流不耗，给你起点终点，问最小体力花费。

题解：当要走的点跟当前点海浪方向相同，relax内不用加1，否则加1（花费），而0-1判断为，当海浪方向相同时，优先走，放入队前，否则放入队后。

#include<bits/stdc++.h>
#define MEM(a,x) memset(a,x,sizeof(a));
#define MEMINF(a) memset(a,0x3f,sizeof(a));

using namespace std;
typedef long long LL;
const int MAXN=1e3+10;
const int INF=0x3f3f3f3f;
int dx[8]={-1,-1,0,1,1,1,0,-1};
int dy[8]={0,1,1,1,0,-1,-1,-1};

struct Node {
  int x,y;
}s,t,now,nex;

bool vis[MAXN][MAXN];
int dis[MAXN][MAXN];
int n,m,k;
char mp[MAXN][MAXN];
void bfs() {
  deque<Node>q;
  q.push_front(s);
  dis[s.x][s.y]=0;
  while (!q.empty()) {
    now=q.front();
    q.pop_front();
    if (now.x==t.x&&now.y==t.y) break;
    if (vis[now.x][now.y]) continue;
    vis[now.x][now.y]=1;
    for (int i=0; i<8; ++i) {
      nex=now;
      nex.x+=dx[i];
      nex.y+=dy[i];
      if (nex.x<1||nex.x>n||nex.y<1||nex.y>m) continue;
      int flag=0;
      if (mp[now.x][now.y]-'0'==i) flag=1;
      if (dis[now.x][now.y]+!flag<dis[nex.x][nex.y]) {
        dis[nex.x][nex.y]=dis[now.x][now.y]+!flag;
        if (flag) q.push_front(nex);
        else q.push_back(nex);
      }
    }
  }
}
int main() {
  cin>>n>>m;
  for (int i=1; i<=n; ++i)
   scanf("%s",mp[i]+1);
  cin>>k;
  for (int i=0; i<k; ++i) {
   scanf("%d %d %d %d",&s.x,&s.y,&t.x,&t.y);
   MEMINF(dis);
   MEM(vis,0);
   bfs(); 
   printf("%d\n",dis[t.x][t.y]);
  }
}

Codeforces 590C Three States

题目

题意：给你一张n×m的图，#不可修路，‘.' 可修路，1,2,3分别代表三个不同国家的城市（可以有多个），问最少修多少个方格的路能把所有国家联通。

题解：对每个国家进行bfs，找出其任意城市到每一点最少需要修多少个方格的路，然后最后对三种不同国家遍历相加，找出三国到一点最少花费和，（若这一点为‘.'则要减去2避免重复），0-1判断为，优先不是点的路，避免增加花费，放入队前，否则放入队后。

#include<bits/stdc++.h>
#define MEM(a,x) memset(a,x,sizeof(a));
#define MEMINF(a) memset(a,0x3f,sizeof(a));
using namespace std;
typedef long long LL;
const int MAXN=1e3+10;
const int INF=0x3f3f3f3f;
const int MOD=1000000007;
char mp[MAXN][MAXN];
bool vis[MAXN][MAXN];
int dis[4][MAXN][MAXN];
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int n,m;

struct Node {
  int x,y;
}now,nex;
void bfs(int num) {
  MEMINF(dis[num]);
  MEM(vis,0);
  deque<Node>q;
  Node s;
  for (int i=1 ; i<=n; ++i) {
    for (int j=1; j<=m; ++j) {
      if (mp[i][j]==num+'0') {
        s.x=i;
        s.y=j;
        q.push_front(s);
        dis[num][i][j]=0;
      }
    }
  }
  while(!q.empty())  {
    now=q.front();
    q.pop_front();
    if (vis[now.x][now.y]) continue;
    vis[now.x][now.y]=true;
    for (int i=0; i<4; ++i) {
      nex=now;
      nex.x+=dx[i];
      nex.y+=dy[i];
      if (nex.x<1||nex.x>n||nex.y<1||nex.y>m||mp[nex.x][nex.y]=='#') continue;
      int step=0;
      if (mp[nex.x][nex.y]=='.') step=1;
      if (dis[num][nex.x][nex.y]>dis[num][now.x][now.y]+step){
        dis[num][nex.x][nex.y]=dis[num][now.x][now.y]+step;
        if (mp[now.x][now.y]=='.'||mp[nex.x][nex.y]=='.') q.push_back(nex);
        else q.push_front(nex);
      }
    }
  }
}



    
int main() {
  cin>>n>>m;
  for (int i=1; i<=n; ++i) 
    scanf("%s",mp[i]+1);
  MEMINF(dis);
  bfs(1);
  bfs(2);
  bfs(3);
  int ans=INF;
  /*
  for (int i=1; i<=3; ++i) {
    for (int j=1; j<=n; ++j) {
      for (int k=1; k<=m; ++k) {
        printf("%10d\t",dis[i][j][k]);
      }
      puts("");
    }
    puts("\n");
  }

  */
   for (int i=1; i<=n; ++i) {
    for (int j=1; j<=m; ++j) {
      if (mp[i][j]=='#') continue;
      if (dis[1][i][j]==INF||dis[2][i][j]==INF||dis[3][i][j]==INF) continue;
      int flag=0;
        if (mp[i][j]=='.') flag=2;
      if (ans>dis[1][i][j]+dis[2][i][j]+dis[3][i][j]-flag) {
        ans=dis[1][i][j]+dis[2][i][j]+dis[3][i][j]-flag;
      }
    }
  }
  if (ans==INF) puts("-1");
  else printf("%d\n",ans);
}



Gym 100625J  Jailbreak

题意：n×m的图代表墙，有两个$符号代表犯人，#代表门，*代表墙，' . '代表路，打开一个门需要耗时，走路不需要耗时，当一个犯人打开一扇门后，该门便一直处于打开状态，问最少需要打开多少扇门，才能使两个犯人都逃出去。

题解：跟上面那题一模一样，换个壳子，我们只要统计每个犯人到每个点的最小开门数，然后求边界上每个非墙点到图内每个点的最小开门数，然后枚举相加找最小值就好了。

0-1判断为优先走路，front，否则back。

代码：

#include<bits/stdc++.h>
#define MEM(a,x) memset(a,x,sizeof(a));
#define MEMINF(a) memset((a),0x3f,sizeof(a));
using namespace std;
typedef long long LL;
const int MAXN=1e2+10;
const int INF=0x3f3f3f3f;
const int MOD=1000000007;
int dx[]={1,0,-1,0};
int dy[]={0,-1,0,1};
int n,m;
char mp[MAXN][MAXN];
int dis[500][MAXN][MAXN];
struct node {
  int x,y;
}s;
vector<node>res;
vector<node>pris;

bool vis[MAXN][MAXN];
void bfs(int num) {
  MEM(vis,false);
  deque<node>q;
  q.push_front(s);
  dis[num][s.x][s.y]=0;
  if (mp[s.x][s.y]=='#') dis[num][s.x][s.y]=1;
  while (!q.empty()) {
    node now=q.front();
    q.pop_front();
    if (vis[now.x][now.y]) continue;
    vis[now.x][now.y]=true;
    for (int i=0; i<4; ++i) {
      node nex=now;
      nex.x+=dx[i];
      nex.y+=dy[i];
      if (nex.x<1||nex.x>n||nex.y<1||nex.y>m) continue;
      if (mp[nex.x][nex.y]=='*') continue;
      int flag=0;
      if (mp[nex.x][nex.y]=='#') flag=1;
      if (dis[num][nex.x][nex.y]>dis[num][now.x][now.y]+flag) {
        dis[num][nex.x][nex.y]=dis[num][now.x][now.y]+flag;
        if (flag) q.push_back(nex);
        else q.push_front(nex);
      }
    }
  }
}


int main () {
  int T;
  cin>>T;
  while (T--) {
    pris.clear();
    res.clear();
    MEMINF(dis);
    cin>>n>>m;
   node temp;
   int cnt=0;
    for (int i=1; i<=n; ++i) {
      scanf("%s",mp[i]+1);
      for (int j=1; j<=m; ++j) {
        temp.x=i,temp.y=j;
        if (mp[i][j]=='$') pris.push_back(temp);
        if (mp[i][j]!='*'&&(i==1||i==n||j==1||j==m))res.push_back(temp);
      }
    }
    
    for (int i=0; i<pris.size(); i++) {
      s=pris[i];
      bfs(i);
      cnt++;
    }
    for (int i=0; i<res.size(); ++i) {
      s=res[i];
      bfs(i+2);
      cnt++;
    }
    int ans=INF;
    /*
    for (int i=0; i<cnt; ++i) {
      for (int j=1; j<=n; ++j) {
        for (int k=1; k<=m; ++k) {
          if (dis[i][j][k]==INF) printf("INF  ");
          else printf("%3d  ",dis[i][j][k]);
        }
        puts("");
      }
      puts("\n");
    }
    */
    for (int i=2; i<cnt; ++i) {
      for (int j=1; j<=n; ++j) {
        for (int k=1; k<=m; ++k) {
          if (mp[j][k]=='*')continue;
          if (dis[0][j][k]==INF||dis[1][j][k]==INF||dis[i][j][k]==INF) continue;
          int flag=0;
          if (mp[j][k]=='#') flag=2;
          ans=min(ans,dis[0][j][k]+dis[1][j][k]+dis[i][j][k]-flag);
        }
      }
    }
    printf("%d\n",ans);
  }
}


UVALive 6011 Error

题意：有n对机场，每对机场都可买去程和回程票，现给k张票，代表已经买的，要求从s到t，在最少需要再买的票数情况下，中转次数也要最少。

代码：

#include<bits/stdc++.h>
#define MEM(a,x) memset(a,x,sizeof(a));
#define MEMINF(a) memset(a,0x3f,sizeof(a));
using namespace std;
typedef long long LL;
const int MAXN=1e6;
const int INF=0x3f3f3f3f;
const int MOD=1000000007;
int HASH(char *s) {
  return (s[0]-'A')*26*26+(s[1]-'A')*26+(s[2]-'A');
}
int s,t;
struct Edge{
  int u,v,w;
  int nex;
}edge[MAXN];
int head[MAXN];
int top;
void Addedge(int u,int v,int w) {
  edge[top].v=v,edge[top].nex=head[u],edge[top].w=w,head[u]=top++;
}

int dis[MAXN];
int booking[MAXN];
void bfs() {
  deque<int>q;
  q.push_front(s);
  dis[s]=0;
  int u,v;
  booking[s]=0;
  while(!q.empty()) {
    u=q.front();
    q.pop_front();
    for (int p=head[u]; ~p; p=edge[p].nex) {
      v=edge[p].v;
      if (booking[v]>booking[u]+1) {
        booking[v]=booking[u]+1;
        dis[v]=dis[u]+edge[p].w;
        q.push_back(v);
      }
      else {
        if (booking[v]==booking[u]+1&&dis[v]>dis[u]+edge[p].w) {
          dis[v]=dis[u]+edge[p].w;
          q.push_front(v);
        }
      }
    }
  }
  printf("%d\n",dis[t]);
}
string st,ed;

int main() {
  int T;
  cin>>T;
  while (T--) {
    MEM(dis,0);
    MEMINF(booking);
    MEM(head,-1);
    top=0;
    int n;
    scanf("%d",&n);
    char a[4];
    char b[4];
    for (int i=0; i<n; ++i) {
      scanf("%s %s",a,b);
      int ha=HASH(a);
      int hb=HASH(b);
      Addedge(ha,hb,1);
      Addedge(hb,ha,1);
    }
    int ha,hb;
    cin>>n;
    for (int i=0; i<=n; ++i) {
      if (i==0) {
        scanf("%s",a);
        ha=HASH(a);
        st=a;
        s=ha;
        continue;
      }
      hb=ha;
      scanf("%s",a);
      ha=HASH(a);
      Addedge(hb,ha,0);
    }
    ed=a;
    t=ha;
    bfs();
  }
}


标签：

相关文章