BFS.cpp

#include <iostream>
#include <utility>
#include <queue>
using namespace std;

#define TRASH 1
#define VISITED 2
#define SIZE 3

int rooms[3][3] = {
    {1, 1, 1},
    {0, 0, 0},
    {0, 0, 0}
};
int visited[3][3] = {0};

queue<pair<int, int>> q;

void BFS(pair<int, int> initial){
    // add init node to queue
    q.push(initial);
    // mark as visited
    visited[initial.first][initial.second] = VISITED;
    int i, j;
    while (!q.empty()){
        pair<int, int> u = q.front();
        q.pop();
        i = u.first;
        j = u.second;
        cout << "Visited position (" << i << ", " << j <<")!\n";
        if (rooms[i][j] == TRASH) {
            cout << "Found trash at position (" << i << ", " << j << ")!\n";
        }
        // discover
        // left
        // if we have left node, and the node not visit yet, add it to queue. Similar with right, top and bottom
        if (j - 1 >= 0 && visited[i][j-1] != VISITED){
            q.push(make_pair(i, j-1));
            cout << "Discover position (" << i << ", " << j - 1<<")!\n";
            visited[i][j-1] = VISITED;
        }
        // right
        if (j + 1 < SIZE && visited[i][j+1] != VISITED){
            q.push(make_pair(i, j+1));
            cout << "Discover position (" << i << ", " << j + 1<<")!\n";
            visited[i][j+1] = VISITED;
        }
        // top
        if (i - 1 >= 0 && visited[i-1][j] != VISITED){
            q.push(make_pair(i-1, j));
            cout << "Discover position (" << i - 1 << ", " << j << ")!\n";
            visited[i-1][j] = VISITED;
        }
        // bottom
        if (i + 1 < SIZE && visited[i+1][j] != VISITED){
            q.push(make_pair(i+1, j));
            cout << "Discover position (" << i + 1 << ", " << j << ")!\n";
            visited[i+1][j] = VISITED;
        }
        cout << "====================\n";
    }
    cout << "Program finished!\n";
}

int main(){
   pair<int, int> init_state = make_pair(2, 1);
   BFS(init_state);
}