Hanoi tower in C++

Here I'm sending a recursive solution for solving Hanoi tower problem with 3 columns and n disks.
Columns are in following order :

    ||                ||             ||
    ||                ||             ||
    ||                ||             ||
    ||                ||             ||
====         ====      ====
 c_from         c_other         c_to

The problem is moving n disks from column c_from to column c_to ( we can't put bigger disks over smaller disks in a column )
Solution is :
1- moving n-1 disks from c_from to c_other
2- moving last disk from c_from to c_to
3- moving n-1 disks from c_other to c_to
.
here is simple code in C++ to solve the problem:

class HanoiTower
{
 
private :
 int N;
 stack<int> towers[3];
public:
 enum TOWERS
 {
  A=0,
  B=1,
  C=2
 };
 HanoiTower(int pN)
 {
  N=pN;
  for(int i=N-1;i>=0;i--)
   towers[A].Push(i);
 }
 void MoveRec(int pN,TOWERS tFrom,TOWERS tTo)
 { 
  if(pN==0)
  {
   int disk=towers[tFrom].Top();
   towers[tFrom].Pop();
   towers[tTo].Push(disk);
   cout <<" move "<<disk<<" from "<<tFrom<< " to "<< tTo<<endl;
   //cout <<disk+1<<tFrom+1<<tTo+1<<endl;
   return;
  }
  TOWERS other=(TOWERS)(3-tFrom-tTo);
  MoveRec(pN-1,tFrom,other);
  MoveRec(0,tFrom,tTo);
  MoveRec(pN-1,other,tTo);
 }
};

// usage :
HanoiTower hn(15);
hn.MoveRec(14,HanoiTower::TOWERS::A,HanoiTower::TOWERS::C);

Rain water trap problem 2D version

Given a 2D matrix where each element represents the elevation(height) on that point, find how many rain water it is able to hold.(Twitter interview question)

For example, given the below 3×3 matrix:
3 3 3
3 0 3
3 3 3

It should hold 3 units of rain water.

I wrote a code for that and I think It works. I tested it against various inputs and got right answer. Please let me know if something appears wrong.

here is my code :

#pragma once
#include <iostream>
#include <vector>
using namespace std;

vector<vector<int> > Visited;
int HowMuchCanHold(vector<vector<int> > &M,int i,int j)
{
 Visited[i][j]=1;
 if(i==0 || j==0 || i==M.size()-1 || j==M[0].size()-1) // we are in borders
  return -1; // drops to earth
 int up=M[i-1][j],down=M[i+1][j],left=M[i][j-1],right=M[i][j+1];
 int minall=1<<10;
 if(!Visited[i-1][j])
  minall=min(minall,up);
 if(!Visited[i+1][j])
  minall=min(minall,down);
 if(!Visited[i][j-1])
  minall=min(minall,left);
 if(!Visited[i][j+1])
  minall=min(minall,right);
 
 int mij=M[i][j];
 if(minall>mij)
  return minall-mij;
 else
  if(minall<mij)
   return -1; // can't hold the drop
 
 int minup=1<<10,mindown=1<<10,minleft=1<<10,minright=1<<10;
 if(mij==up && Visited[i-1][j]==0) // drop may flow up
  minup=HowMuchCanHold(M,i-1,j);
 else
  if(mij!=up)
   minup=up-mij;
 if(mij==down && Visited[i+1][j]==0) // drop may flow down
  mindown=HowMuchCanHold(M,i+1,j);
 else
  if(mij!=down)
   mindown=down-mij;
 if(mij==left && Visited[i][j-1]==0) // drop may flow left
  minleft=HowMuchCanHold(M,i,j-1);
 else
  if(mij!=left)
   minleft=left-mij;
 if(mij==right && Visited[i][j+1]==0) // drop may flow right
  minright=HowMuchCanHold(M,i,j+1);
 else
  if(mij!=right)
   minright=right-mij;
 if(minup<0 || mindown<0 || minleft<0 || minright <0) // drop wil fall from up,down,left or right!
  return -1; // can't hold the drop
  int min1=min(minup,mindown);
  int min2=min(minleft,minright);
  minall=min(min1,min2);
  return minall;
}
int DropTo(vector<vector<int> > &M,int i,int j)
{
  Visited=vector<vector<int> >(M.size(), vector<int>(M[0].size(),0));
  return HowMuchCanHold(M,i,j);
}
int get_watr_trap(vector<vector<int> > M)
{
 int row=M.size();
 int col=M[0].size();
 int total=0;
 int nexthold=0;
 bool find=false;
 while(1)
 {
  find=false;
  for(int i=0;i<row;i++)
  {
   for(int j=0;j<col;j++)
   {
    nexthold=DropTo(M,i,j);
    if(nexthold>0)
    {
     find=true;
     M[i][j]+=nexthold;//fill current cell up to the maxhold
     total+=nexthold;
    }
   }
  }
  if(!find)
   break;
 }
 return total;
}
void test_water_trap()
{
 vector<vector<int> > M(4, vector<int>(4,10));
 M[1][1]=0;
 M[1][2]=2;
 M[2][1]=4;
 M[2][2]=8;
 M[3][0]=2;
 M[3][2]=8;
 int water_trapped=get_watr_trap(M);
 cout << water_trapped << endl;
}

Min Coin Change problem using DP and backtracking

Suppose we have set of coins S={c1,c2,c3,...cn} and M
we need to find smallest number of coins to change M.
or find all <kj,cj> such that Sum ( kj*cj ) = M

Solution:
I used dynamic programming to solve the problem and also used backtracking to return all <kj,cj>:

for more information have a look at :
http://www.algorithmist.com/index.php/Min-Coin_Change

----------------------------------------------

map<int,int> min_coins(vector<int> pCoins,int pSum,int *pMinRequired)
{
 map<int,int> trace;//(pCoins.size());
 vector<int> mins(pSum+1);
 vector<int> prev(pSum+1);
 fill(mins.begin(),mins.end(),INFINITY);
 for(int i=0;i<pCoins.size();i++)
  trace.insert(make_pair<int,int>(pCoins[i],0));
 mins[0]=0;
 sort(pCoins.begin(),pCoins.end());
 for(int i=1;i<=pSum;i++)
 {
  int bestCoin=-1;
  for(int v=0;v<pCoins.size() && pCoins[v]<=i  ;v++)
   if(mins[i-pCoins[v]]+1<mins[i])
   {
    mins[i]=mins[i-pCoins[v]]+1;
    bestCoin=v;
    prev[i]=i-pCoins[v];
   }
   if(bestCoin !=-1)
    trace[i]=pCoins[bestCoin];
 }
 *pMinRequired= mins[pSum];
 int curr=pSum;
 map<int,int> ret;
 while(curr>0)
 {
  ret[trace[curr]]++;
  curr=prev[curr];
 }
 return  ret;
}

 void test_coins()
{
 vector<int> coins;
 coins.push_back(1);
 coins.push_back(5);
 coins.push_back(10);
 coins.push_back(25);
 int minreq,sum=30;
 map<int,int> result=min_coins(coins,sum,&minreq);
 cout << " min required for "<<sum<<"$ is to pick "<<minreq<<" coins as :"<<endl;
 for(map<int,int>::iterator it=result.begin();it!=result.end();it++)
  cout <<" pick "<<it->second <<" coins of "<<it->first<<endl;

}

---------------------------------------------

A* path finding algorithm


You can find it in my Google+ ProPro page

How to implement T9 contact search in C++ using Trie-Trees ?

please look at my G+ ProPro Page