BFS

Wiki

Applications of BFS

Breadth-first search can be used to solve many problems in graph theory, for example:

• Finding all connected components in a graph.
• Finding all nodes within one connected component
• Copying Collection, Cheney's algorithm
• Finding the shortest path between two nodes u and v (in an unweighted graph)
• Finding the shortest path between two nodes u and v (in a weighted graph: see talk page)
• Testing a graph for bipartiteness
• (Reverse) Cuthill–McKee mesh numbering

topcoder example: use BFS to check graph connectivity

/*
Graph is considered to be stored as adjacent vertices list.
Also we considered graph undirected.
 
vvi is vector< vector<int> >
W[v] is the list of vertices adjacent to v

tr is the macro to get iterator and try each element
*/
 int N; // number of vertices
 vvi W; // lists of adjacent vertices   
 bool check_graph_connected_bfs() { 
      int start_vertex = 0; 
      vi V(N, false); 
      queue<int> Q; 
      Q.push(start_vertex); 
      V[start_vertex] = true; 
      while(!Q.empty()) { 
           int i = Q.front(); 
           // get the tail element from queue
           Q.pop(); 
           tr(W[i], it) { 
                if(!V[*it]) { 
                     V[*it] = true; 
                     Q.push(*it); 
                } 
           } 
      } 
      return (find(all(V), 0) == V.end()); 
 }  

Problem 

• UVa 11501 - Laurel Creek

input :

7 11
....S......
....|......
B---S......
...........
...........
...........
....S.S...E

• 7 11 : row and column size
  
• B: starting position;
  
• E: end position;
  
• S: intermediate stump;
  
• - or | : connecting logs
  
• .  empty (water)
  
• constraints: row and column size <= 15,  stumps # <= 15, all logs exist between stumps

一开始就用了BFS，做起来发现状态太多了。难点就在于怎样记录已经访问过的状态。开始试了一种状态表示，后来证明是错误的。当时用current pos + 该点四周logs的分布情况作为一个单独的状态，其实这是不行的。这种表示方法无法求解出下面这种情况，因为一个状态不仅跟自己所处位置的log相关，还跟其它位置的logs分布也相关。

....S...S..
........|..
B-----S.|.E
......|.|..
......|.S..
......|....
....S-S....

后来先后用了两种方法减少状态空间。利用了这个前提：stumps是固定的，变化的是自己的位置和logs的位置。

• 用一个2D-bitvector (nrow+1)x ncol 记录图中所有log的位置，每个位对应一个'-' 或者 '|', 多出来的一行用来表示当前位置(x* ncol + y)。整个2d-vector作为一个状态存入一个set visited,之后通过查询visited 中是否有该状态存在得知此状态是否访问过。这个版本由于用了stl set 速度比较慢（在测试数据上用的时间是第二种方法的15倍），但可以用于slots比较多的情况。

vector<int> bitlog;

for(int i = 0; i < nrow; ++i)
   for(int j = 0; j < ncol; ++j)
      if(m[i][j] == '-' || m[i][j] == '|')
          bitlog[i] = bitlog[i] | (1<<j);
bitlog[nrow] = start.first*ncol+start.second;

     set<vector<int> > visited;

在BFS里queue里的元素用了以下类型

struct State{
    ii pos;   // current position
    int log;  // log length
    vector<string> maze; // graph
    vector<int> bitlog;  // 2d bitvector
    int step; // current step
}

• Considering the available slots where the log can be picked up or put down, the state space is not that big. Because there are at most 15 stumps with limited row and column size(<= 15) and logs only exist between stumps, the following case is the one that comes with the greatest number of logs. right?




• S-S-S-S
|.|.|.|
S-S-S-S
|.|.|.|
S-S-S-S
|.|.|.|
S-S-S-.

There are less than 24 positions that logs can be put down. Also the current position can be represented with 4 bits (we can only stand on a stump), so the state space can be represented as 4bit + 24bit = 28 bits.  如果有只有7个available slots for logs那么我们的bitvector只用11位就可以了。比如，0110|0110110, 表示现在我们的位置是第6号stump,图中有4个logs，共有7处slots(当然不同长度的log必须放在其相应的slots中，对每个log而言，可能没有7处可用的slots.)

#include <iostream>
#include <queue>
#include <ctime>
#include <map>
using namespace std;

typedef pair<int,int> ii;

struct State{
public:
    int status;// current position + log position
    int log;   // log length in hand
    int step;  // current step (for outputing shortest step to destination
    State(int st, int l, int s):status(st), log(l), step(s){}
};

// get log width, pos1/pos2 are stumps position
inline int length(ii pos1, ii pos2) {
    if(pos1.first == pos2.first) return abs(pos1.second-pos2.second)-1;
    return abs(pos1.first-pos2.first)-1;
}

int BFS(int start, int dest, map<int, ii> &stumppos,
        map<int, ii> &slotpos, map<ii,int> &slotlist, int status) {
    if(start == dest) return 0;

    // total available slots to put down or pickup logs
    int totalslots = slotlist.size();

    // make and clear all visited state
    // a bit vector: highest 4 bit --- current position (stump id#)
    // the rest bits: all correspond to an available slot

    // use int* instead of vector<int>, the former is a bit faster 
    int *v = new int[(1<< (totalslots + 4))-1];
    memset(v, 0, sizeof(int)*((1<< (totalslots + 4))-1));

    queue<State> Q;
    Q.push(State(status, 0, 0));
    v[status] = 1;

    while(!Q.empty()) {
        State s = Q.front();
        Q.pop();

        // current position in terms of stump id#
        int uid = s.status >> totalslots;
        // current position in terms of (row,col)
        ii u = stumppos[uid];

       // for each available log
        // i : slots id
        for(int i = 0; i < totalslots; ++i) if(s.status & (1<<i)) {
            ii logpair = slotpos[i];
            // find a connecting log
            if(uid == logpair.first || uid == logpair.second) {
                int next = uid == logpair.first? logpair.second: logpair.first;
                if(next == dest) {
                    delete [] v; // free visited state memory
                    return s.step+1;
                }
                // move to the next stump
                int ns = (s.status ^ (uid << totalslots)) | (next << totalslots);
                if(v[ns] == 0) {
                    v[ns] = 1;
                    Q.push(State(ns, s.log, s.step+1));
                }              

                if(s.log) continue;
                // pick up a log
                ns = s.status ^ (1<<i);
                if(v[ns] == 0) {
                    v[ns] = 1; 
                    // log width
                    int width = length(stumppos[logpair.first], stumppos[logpair.second]);
                    Q.push(State(ns, width, s.step+1));
                }
            }
        }

        map<ii,int>::iterator slot_it = slotlist.begin();
        map<ii,int>::iterator slot_end= slotlist.end();
        for(; slot_it!= slot_end; ++slot_it) {
            ii slot_pair = slot_it->first;
            int i = slot_pair.first;
            int j = slot_pair.second; 
            if(i != uid && j != uid) continue;
            
            if(length(stumppos[i],stumppos[j]) != s.log) continue;
            ii vv = i == uid ? stumppos[j] : stumppos[i];

            // first, check there is no log between them      
            if(s.status & (1<< slot_it->second)) continue;

            bool found = false;
            // second, check there are no other logs go through any points between them
            bool h1 = u.first == vv.first;
            for(int i = 0; i < totalslots; ++i) if(s.status & (1<<i)) {
                ii logpair = slotpos[i];
                ii pos1 = stumppos[logpair.first];
                ii pos2 = stumppos[logpair.second];

                bool  h2 = (pos1.first == pos2.first);
                if(h1 == h2) continue;
                if(h1 && pos1.first < u.first && pos2.first > u.first &&
                    u.second < pos1.second && vv.second > pos1.second) {
                    found = true;break;
                }
                if(h2 && pos1.second < u.second && pos2.second > u.second &&
                    u.first < pos1.first && vv.first > pos1.first) {
                        found = true; break;
                } 
            }
            if(found) continue;     
            int ns = s.status | (1<<slot_it->second);
            if(v[ns] == 0) {
                v[ns] = 1;
                Q.push(State(ns, 0, s.step+1));
            }           
        }        
    }
    delete []v;
    return 0;
}

// pre-calculate stump pairs, log positin, etc...
int get_adj(char m[15][15], map<int, ii> &stumppos, map<ii,int> &stumplist,
             map<int, ii> &slotpos, map<ii,int> &slotlist, int &slot_status,
             int& start, int& dest, int nrow, int ncol) {
    const short MAXDIR = 4;
    //   down, up, left, right
    const short dx[MAXDIR] = {1,-1,0, 0};
    const short dy[MAXDIR] = {0, 0,-1,1};
    const char  dl[MAXDIR] = {'|', '|', '-', '-'};

    for(int i = 0; i < nrow; ++i)
        for(int j = 0; j < ncol; ++j)
            if(m[i][j] == 'S' || m[i][j] == 'E' || m[i][j] == 'B') {
                if(m[i][j] == 'B') start = stumplist.size();
                if(m[i][j] == 'E') dest  = stumplist.size();
                stumplist.insert(make_pair(ii(i,j), stumplist.size()));
                stumppos.insert(make_pair(stumplist.size()-1, ii(i,j)));
            }
    // for each stump, scan for available slot to put down logs
    for(int j = 0; j < stumplist.size(); ++j){
        int x = stumppos[j].first;
        int y = stumppos[j].second;
        bool flag;
        for(int i = 0; i < MAXDIR; ++i) {
            int nx = x, ny = y;
            flag = false;
            do{
                nx = nx + dx[i];
                ny = ny + dy[i];
                if(nx<0 || nx >= nrow || ny < 0 || ny >= ncol) {
                    flag = true; break;
                }
                if(m[nx][ny] == 'S' || m[nx][ny] == 'E' || m[nx][ny] == 'B') break;
            } while(true);
            if(flag) continue;
            int logLen = max(abs(nx-x), abs(ny-y));
            if(logLen > 1 && (m[nx][ny] == 'S' || m[nx][ny] == 'E' || m[nx][ny] == 'B')) {
                int idnext = stumplist[ii(nx,ny)];
                ii logpos = j < idnext? ii(j, idnext) : ii(idnext, j);
                slotlist.insert(make_pair(logpos, slotlist.size()));
                slotpos.insert(make_pair(slotlist.size()-1, logpos));
            }
        }
    }
    int totalslots = slotlist.size();
    
    slot_status = 0;
    // scan for existing logs
    for(int j = 0; j < stumplist.size(); ++j){
        int x = stumppos[j].first;
        int y = stumppos[j].second;
        bool flag;
        for(int i = 0; i < MAXDIR; ++i) {
            int nx = x, ny = y;
            flag = false;
            do{
                nx = nx + dx[i];
                ny = ny + dy[i];
                if(nx<0 || nx >= nrow || ny < 0 || ny >= ncol) flag = true;
            } while(!flag && m[nx][ny] == dl[i]);

            if(flag) continue;
            int logLen = max(abs(nx-x), abs(ny-y));
            if(logLen > 1 && (m[nx][ny] == 'S' || m[nx][ny] == 'E' || m[nx][ny] == 'B')) {
                int idnext = stumplist[ii(nx,ny)];
                ii logpos = j < idnext? ii(j, idnext) : ii(idnext, j);
                slot_status |= (1<< slotlist[logpos]);
            }
        }
    }
    return totalslots;
}

int main() {
    int ndata;
    scanf("%d ", &ndata);
    char m[15][15]; // maze
    for(int data = 0; data < ndata; data++) {
        int nrow, ncol;
        scanf("%d %d ", &nrow, &ncol);
        for(int i = 0; i < nrow; ++i)
            scanf("%s ", &m[i]);
        map<ii, int> stumplist;
        map<int, ii> stumppos;
        map<ii,int> slotlist;
        map<int,ii> slotpos;
        
        int status, start, dest;
        int totalslots = get_adj(m, stumppos, stumplist, slotpos, slotlist, 
            status, start, dest, nrow, ncol);
        status |= (start<<totalslots);
        printf("%d\n", BFS(start, dest, stumppos, slotpos, slotlist, status));
    }
    return 0;
}