using namespace std;

#include <stdio.h>
#include <vector>

int map[10][10]={{0,0,0,0,0,0,0,0,0,0},
                 {1,1,1,1,0,0,0,0,0,0},
                 {0,1,0,1,0,0,0,0,0,0},
                 {0,1,0,1,0,1,1,1,1,1},
                 {0,1,1,1,0,1,0,0,0,0},             
                 {0,0,0,0,0,1,0,0,0,0},
                 {0,0,0,0,0,1,0,0,0,0},             
                 {0,0,0,0,0,1,0,0,0,0},
                 {0,0,0,0,0,1,0,0,0,0},             
                 {0,0,0,0,0,0,0,0,0,0}};
             
int map1[10][10]={{0,0,0,0,0,0,0,0,0,0},
                 {1,1,1,1,0,0,0,0,0,0},
                 {0,1,0,1,0,0,0,0,0,0},
                 {0,1,0,1,0,1,1,1,1,1},
                 {0,1,1,1,0,1,0,0,0,0},             
                 {0,0,0,0,0,1,0,0,0,0},
                 {0,0,0,0,0,1,0,0,0,0},             
                 {0,0,0,0,0,1,0,0,0,0},
                 {0,0,0,0,0,1,0,0,0,0},             
                 {0,0,0,0,0,0,0,0,0,0}};
             
struct node_info
{
  void *node;
  node_info *parent_info;
  int h;
  int g;
};

int h(void *s)
{
  int *t=(int *)s;
  return 9-t[0]+9-t[1];
}

int cmp(void *s1, void *s2)
{
  int *t1=(int *)s1;
  int *t2=(int *)s2;
  return t1[0]==t2[0] && t1[1]==t2[1];
}

void succ(void *node, vector<void *> *successors, vector<int> *costs)
{
  int i,j;
  int *n=(int *)node;
  int *tmp;
  successors->clear();
  costs->clear();
  
  for(i=-1; i<=1; i++)
    for(j=-1; j<=1; j++)
      if(i==0 && j==0 || n[0]+i<0 || n[0]+i>9 || 
          n[1]+j<0 || n[1]+j>9 || map[n[0]+i][n[1]+j])
        continue;
      else
      {
        tmp=(int *)malloc(2*sizeof(int));
        tmp[0]=n[0]+i;
        tmp[1]=n[1]+j;
        successors->push_back(tmp);
        costs->push_back(1);
      }
}


int astar(void *start,
          void *finish,
          int (*h)(void *),
          int (*cmp)(void *, void *),
          void (*succ)(void *, vector<void *> *, vector<int> *),
          vector<node_info> *path)
{
  vector<node_info *> open_list;
  vector<node_info *> closed_list;
  vector<void *> successors;
  vector<int> costs;
  node_info *current_node_info;
  node_info *tmp;
  int path_found=0;
  int i,j;
  
  /* Dodavanje polaznog cvora u otvorenu listu */
  tmp=(node_info *)malloc(sizeof(node_info));
  tmp->node=start;
  tmp->parent_info=NULL;
  tmp->g=0;
  tmp->h=h(start);
  open_list.push_back(tmp);
  map1[((int*)start)[0]][((int*)start)[1]]=2;
  
  while(open_list.size()>0)
  {
    /* Nalazenje cvora sa najmanjom vrednoscu f(n) */
    int min_ind=0;
    for(i=1; i<open_list.size(); i++)
      if(open_list[i]->h+open_list[i]->g < 
          open_list[min_ind]->h+open_list[min_ind]->g)
        min_ind=i;
    current_node_info=open_list[min_ind];
    
    /* Provera da li smo nasli krajnji cvor */
    
    if(cmp(finish,current_node_info->node))
    {
      path_found=1;
      break;
    }
    
    succ(current_node_info->node, &successors, &costs);
    
    for(i=0; i<successors.size(); i++)
    {
      /* Preskakanje naslednika koji su u zatvorenoj listi */
      for(j=0; j<closed_list.size(); j++)
        if(cmp(successors[i],closed_list[j]->node))
          break;
      if(j<closed_list.size())
        continue;
        
      /* Trazimo naslednika u otvorenoj listi */
      
      for(j=0; j<open_list.size(); j++)
        if(cmp(successors[i],open_list[j]->node))
          break;
      
      if(j==open_list.size())
      {
        /* Dodavanje u listu */
        tmp=(node_info *)malloc(sizeof(node_info));
        tmp->node=successors[i];
        tmp->parent_info=current_node_info;
        tmp->g=current_node_info->g+costs[i];
        tmp->h=h(successors[i]);
        open_list.push_back(tmp);
        map1[((int*)successors[i])[0]][((int*)successors[i])[1]]=2;
      }
      else
      {
        /* Eventualna korekcija puta do cvora naslednika koji je vec u listi */
        if(current_node_info->g+costs[i]<open_list[j]->g)
        {
          open_list[j]->parent_info=current_node_info;
          open_list[j]->g=current_node_info->g+costs[i];
        }
      }  
    }
    /* Premestanje tekuceg cvora iz otvorene u zatvorenu listu */
    open_list.erase(open_list.begin()+min_ind);
    closed_list.push_back(current_node_info);
  }
  
  /* Konstrukcija puta */
  
  if(path_found)
  {
    path->push_back(*current_node_info);
    while((*path)[path->size()-1].parent_info)
      path->push_back(*(*path)[path->size()-1].parent_info);
  }
  
  /* Dealokacija memorije */
  
  for(i=0; i<closed_list.size(); i++)
    free(closed_list[i]);
  
  return path_found;
}


int main(int argc, char *argv[])
{
  int i,j,k;
  vector<node_info> path;
  int start[]={0,0};
  int finish[]={9,9};
  
  if(astar(start,finish,h,cmp,succ,&path))
  {
    /* Prikazujemo put */
    for(i=0; i<10; i++)
    {
      for(j=0; j<10; j++)
      {
        for(k=0; k<path.size(); k++)
          if(((int *)path[k].node)[0]==i && ((int *)path[k].node)[1]==j)
          { 
            putchar('*');
            break;
          }
        if(k==path.size())
        {
          if(map[i][j])
            putchar('O');
          else if(map1[i][j]==2)
            putchar('.');
          else
            putchar(' ');
        }
      }
      putchar('\n');
    }
  }
  else
  {
    printf("Nema puta!\n");
  }


  return 0;
}