A*Star Serach source code in C++

#include <iostream>

#include <string>

#include <map>

#include <queue>

#include <stack>

#include <algorithm>

#include <list>

#include <set>

#include <cmath>

#include <cstring>



#include <stdio.h>

#include <string.h>

#include <sstream>

#include <stdlib.h>

#include <vector>

#include <iomanip>

#include <ctime>



using namespace std;





int dx[]={1,0,-1,0};int dy[]={0,1,0,-1};

int fx,fy,dist[100][100],row,col;



int distance(int x,int y,int p,int q);

int heuristic(int x,int y);

//vector<string>board;

int board[100][100];



struct pq

{

    int x,y,cost,h,total_cost;



    pq(int _x,int _y,int _cost)

    {

        x=_x;y=_y;cost=_cost;

        h=heuristic(x,y);

        total_cost=cost+h;

    }

    bool operator<(const pq &b)const

    {

        return total_cost>b.total_cost;    // Min Priority Queue

    }

};



int distance(int x,int y,int p,int q)

{

    if(board[p][q]>board[x][y]) return 3;

    if(board[p][q]==board[x][y]) return 2;

    return 1;

}





int heuristic(int x,int y)

{

    // manhatan distance

    return abs(x-fx)+abs(y-fy);

}



int astar(int x,int y)

{

    int i,j,m,n,cost,cnt;

    priority_queue<pq>Q;



    Q.push(pq(x,y,0));

    memset(dist,-1,sizeof(dist));



    while(!Q.empty())

    {

        pq P=Q.top();

        Q.pop();

        x=P.x;y=P.y;



        cout<< x<<" "<<y<<endl;

        if(dist[x][y]!=-1) continue;



        dist[x][y]=P.cost+P.h;



        cout<<"here"<<endl;

        for(i=0;i<4;i++)

        {

            m=x+dx[i];

            n=y+dy[i];

            if(m>=0 && m<row && n>=0 && n<col)

            {

                cout<<m<<" "<<n<<endl;

                cost=distance(x,y,m,n);

                Q.push(pq(m,n,cost+P.cost));

            }

        }

    }



}



int main()

{

    int i,j,k,sx,sy,c,p,q;

    string st;

    cout<<"Board Description :"<<endl;

    cin >> k>>c;

    row = k;col = c;

    for(i=0;i<k;i++)

    {

        for(j=0;j<c;j++)

        {

          scanf("%1d",&board[i][j]);

        }



    }

    cout<<"Start :";

    cin >>sx>>sy;

    cout<<"Goal :";

    cin>>fy>>fx;

    astar(sy,sx);

    cout<< dist[fy][fx];



    return 0;

}



/*



5 5

34567

23456

12345

23456

34567



0 2

2 2



*/