Breadth-First Search Algorithm in C++ implementation note

breadth-first search (BFS): Finds a path between two nodes by taking one step down all paths and then immediately backtracking.
– Often implemented by maintaining a queue of vertices to visit

Well.. CCC 2015 is on Feb. 18 so now it’s probably a good time to review all kind of stuff in C++. BFS is an important algorithm for searching paths, and here is how it works.

Pseudocode (CS106B Stanford Lecture note, distributed under CC 2.5 License):

function bfs(v1, v2):
    queue := {v1}.
    mark v 1 as visited.
    
    while queue is not empty:
        dequeue a vertex v from the queue.
        if v is v2:
            a path is found!
        for each unvisited neighbor n of v
            mark n as visited, and enqueue n in queue
     //if we get here, no path exists.

An implementation in C++ follows (CCC 2008 Senior Problem No. 3, did it quickly probably poor code style):

//
//  main.cpp
//  2008CCC
//
//  Created by Yuhui Li on 2015-02-11.
//  Copyright (c) 2015 Yuhui Li. All rights reserved.
//
#include <iostream>
#include <fstream>
#include <sstream>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;

struct Coords {
    int x=0;
    int y=0;
    int steps=0;
}coord;

int main(int argc, const char * argv[]) {
    
    ifstream testFile ("/Users/YuhuiLi/Desktop/CCC/s3.5.in");
    
    string line;
    
    if (testFile.is_open()) {
        getline(testFile,line);
        int numberOfTest =atoi(line.c_str());
        
        for (int i=0;i<numberOfTest;i++) {
            int row;
            int col;
            getline(testFile,line);
            row=atoi(line.c_str());
            getline(testFile,line);
            col=atoi(line.c_str());
            
            vector<vector<char> >board(row, vector<char>(col));
            vector<vector<int> >checks(row, vector<int>(col));
            
            
            for (int j=0;j<row;j++) {
                getline(testFile,line);
                for (int k=0;k<col;k++) {
                    board[j][k]=line[k];
                    checks[j][k]=-1;
                }
            }
            
            
            // BFS
            queue<Coords> qu;
            Coords c1;
            c1.steps=1;
            qu.push(c1);
            checks[0][0]=1;
            
            bool a = false;
            
            while (qu.size()>0) {
                Coords c = qu.front();
                qu.pop();
                
                if (c.x+1==board.size()&&c.y+1==board1.size()) {
                    cout << c.steps << endl;
                    a=true;
                    break;
                }
                
                char ch = board11;
                if (ch=='-') {
                    if (c.x>=0&&c.x<board.size()&&c.y-1>=0&&c.y-1<board1.size()&&board11!='*'&&checks11==-1) {
                        checks11=1;
                        Coords cc;
                        cc.x=c.x;
                        cc.y=c.y-1;
                        cc.steps=c.steps+1;
                        qu.push(cc);
                    }
                    if (c.x>=0&&c.x<board.size()&&c.y+1>=0&&c.y+1<board1.size()&&board11!='*'&&checks11==-1) {
                        checks11=1;
                        Coords cc;
                        cc.x=c.x;
                        cc.y=c.y+1;
                        cc.steps=c.steps+1;
                        qu.push(cc);
                    }
                }
                else if (ch=='|') {
                    if (c.x-1>=0&&c.x-1<board.size()&&c.y>=0&&c.y<board1.size()&&board11!='*'&&checks11==-1) {
                        checks11=1;
                        Coords cc;
                        cc.x=c.x-1;
                        cc.y=c.y;
                        cc.steps=c.steps+1;
                        qu.push(cc);
                    }
                    if (c.x+1>=0&&c.x+1<board.size()&&c.y>=0&&c.y<board1.size()&&board11!='*'&&checks11==-1) {
                        checks11=1;
                        Coords cc;
                        cc.x=c.x+1;
                        cc.y=c.y;
                        cc.steps=c.steps+1;
                        qu.push(cc);
                    }
                }
                else if (ch=='+') {
                    if (c.x-1>=0&&c.x-1<board.size()&&c.y>=0&&c.y<board1.size()&&board11!='*'&&checks11==-1) {
                        checks11=1;
                        Coords cc;
                        cc.x=c.x-1;
                        cc.y=c.y;
                        cc.steps=c.steps+1;
                        qu.push(cc);
                    }
                    if (c.x+1>=0&&c.x+1<board.size()&&c.y>=0&&c.y<board1.size()&&board11!='*'&&checks11==-1) {
                        checks11=1;
                        Coords cc;
                        cc.x=c.x+1;
                        cc.y=c.y;
                        cc.steps=c.steps+1;
                        qu.push(cc);
                    }
                    if (c.x>=0&&c.x<board.size()&&c.y-1>=0&&c.y-1<board1.size()&&board11!='*'&&checks11==-1) {
                        checks11=1;
                        Coords cc;
                        cc.x=c.x;
                        cc.y=c.y-1;
                        cc.steps=c.steps+1;
                        qu.push(cc);
                    }
                    if (c.x>=0&&c.x<board.size()&&c.y+1>=0&&c.y+1<board1.size()&&board11!='*'&&checks11==-1) {
                        checks11=1;
                        Coords cc;
                        cc.x=c.x;
                        cc.y=c.y+1;
                        cc.steps=c.steps+1;
                        qu.push(cc);
                    }
                }
            }
            if (!a) cout << "-1" << endl;
            
        }
    }
    
    return 0;
}

Leave a Reply

Your email address will not be published. Required fields are marked *


You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>