8.2 Imagine a robot sitting on the upper left hand corner of an NxN grid. The robot can only move in two directions: right and down. How many possible paths are there for the robot? FOLLOW UP Imagine certain squares are “off limits”, such that the robot can not step on them. Design an algorithm to get all possible paths for the robot.

/*
recursive : back_track
iterative
*/

#include <iostream>
#include <set>
#include <deque>
#include <utility>

using namespace std;

const int N = 6; //grid dimension

typedef pair<int, int> xypair;

//set PATH element to pointer type? Logically wrong!!
//deque<xypair*>* PATH = new deque<xypair>();

//set OFF element to pointer type? Cause problem in find()
//set<xypair*>* OFF = new set<xypair>();

deque<xypair>* PATH = new deque<xypair>();
set<xypair>* OFF = new set<xypair>();

void print(deque<xypair>* PATH)
{
    for (deque<xypair>::iterator it = PATH->begin(); it != PATH->end(); ++it)
    {
        //cout << '(' << (*it)->first << ',' << *(it)->second << ') '; 
        //this is not perl!!
        cout << '(' << (*it).first << ',' << (*it).second << ") ";
    }
    cout << endl;
}

void findAllPath(xypair* xy)
{
    if (xy->first == N && xy->second == N)
    {
        print(PATH);
    }
    else
    {
        if (xy->first != N)
        {
            ++xy->first;
            
            //my most common syntax error
            //if (OFF.find(xy) == OFF.end())
            
            if (OFF->find(*xy) == OFF->end())
            {
                /*
                BUG : PATH must contain a copy of xy instead of pointer type!
                */
                //PATH->push_back(xy);
                PATH->push_back(*xy);
                findAllPath(xy);
                PATH->pop_back();
            }
            --xy->first;
        }
        
        if (xy->second != N)
        {
            ++xy->second;
            if (OFF->find(*xy) == OFF->end())
            {
                PATH->push_back(*xy);
                findAllPath(xy);
                PATH->pop_back();
            }
            --xy->second;
        }
    }
}


/*
this backTrack is tricky to me, I've never done this way before.
Be very careful and learn
*/
void backTrack(deque<xypair>* stack)
{
    if (stack->empty()) return;
    
    xypair sxy = stack->back();
    while (! PATH->empty())
    {
        xypair pxy = PATH->back();
        if (sxy.first - pxy.first == 1 && sxy.second == pxy.second)
        {
            break;
        }
        if (sxy.second - pxy.second == 1 && sxy.first == pxy.first)
        {
            break;
        }
        PATH->pop_back();
    }
}

void findAllPath_iterative(xypair* xy)
{
    deque<xypair> stack;
    stack.push_back(*xy);
    
    while (! stack.empty())
    {
        //stupid
        //xypair cur = PATH->pop_back();
        xypair cur = stack.back();
        stack.pop_back();
        PATH->push_back(cur);
        
        if (cur.first == N && cur.second == N)
        {
            print(PATH);
            
        }
        else
        {
            ++cur.first;
            if (OFF->find(cur) == OFF->end() && cur.first <= N)
            {
                stack.push_back(cur);
            }
            --cur.first;
            
            
            ++cur.second;
            if (OFF->find(cur) == OFF->end() && cur.second <= N)
            {
                stack.push_back(cur);
            }
            --cur.second;
        }
        
        //iteratively pop_back PATH 
        //in order to restore the status for the next loop.
        backTrack(&stack);
    }
}

int main()
{
    OFF->insert(make_pair(4,2));
    OFF->insert(make_pair(4,3));
    OFF->insert(make_pair(4,4));
    OFF->insert(make_pair(4,5));
    OFF->insert(make_pair(4,6));
    findAllPath(new xypair(0, 0));
    cout << endl;
    findAllPath_iterative(new xypair(0, 0));
    /*
    memory release part omitted
    */
    return 0;    
}