// a-stern algorithmus mit priority queue      // 2004 stefan reiss
#include <iostream>                            //      www.reisz.de
#include <algorithm>       // findet dichtesten weg um hindernisse
#include <ctime>           // von links oben nach rechts unten
using namespace std;

const int maxx = 30 , maxy = 20 , maxp = maxx * maxy;
inline int   getx(int p)  { return p % maxx; }
inline int   gety(int p)  { return p / maxx; } 
const int d8_off[] = {1,1-maxx,-maxx,-1-maxx,-1,-1+maxx,maxx,1+maxx};

#define forint(i,a,b) for(int i=(a);i!=(b);++i)
#define FORNEIGHS(p,np) forint(d,0,8)\
  if(!((d<2||d==7)&&getx(p)==maxx-1) && !((d>=3&&d<6)&&getx(p)==0))\
    if((np=(p)+d8_off[d]) >= 0  &&  np < maxp)

int mincost(int p0 , int p1) // wegkosten im guenstigsten fall
{ int xd = abs(getx(p0)-getx(p1)) , yd = abs(gety(p0)-gety(p1));
  return 141 * _cpp_max(xd,yd) - 41 * abs(xd-yd); }

struct node { int prev,g,h;  bool done; };
// prev= vorg. im weg;  g= cost from start  h= mincost to goal; 

int f[maxp];  node nodes[maxp]; int olist[maxp]; int nolist;
int startp = 0, goalp = maxp-1; // olist ist prio-que. beste zuerst  

bool ncomp(int p0 , int p1) // welcher knoten ist aussichtsreicher
{ return nodes[p0].g+nodes[p0].h > nodes[p1].g+nodes[p1].h; } 

void do_node(int p)
{ int np; f[p] = 3; nodes[p].done = true;
  FORNEIGHS(p,np) if(f[np]!=1) // alle betretbaren nachbarn
  { int g = nodes[p].g + (d&1 ? 141:100); // kosten start->np
    if(!nodes[np].g)         // knoten ist neu
    { nodes[np].g = g; nodes[np].h = mincost(np,goalp);
      nodes[np].prev = p; 
      olist[nolist++]=np; push_heap(olist,olist+nolist,ncomp);
    }
    else if(g < nodes[np].g) // schon bearbeitet aber jetzt besser
    { nodes[np].prev = p; nodes[np].g = g;
      if(nodes[np].done) // move back to open list
      { nodes[np].done = false;
        olist[nolist++]=np; push_heap(olist,olist+nolist,ncomp);
      }
      else // move upwards in open list
      { forint(i,0,nolist) if(olist[i]==np) 
        { push_heap(olist,olist+i,ncomp); break; } 
} } } } 

void main()
{ memset(nodes,0,sizeof(nodes)); forint(x,0,maxp) nodes[x].prev = -1;
  memset(f,0,sizeof(f)); srand(time(0));
  forint(p,0,maxp-1) if(rand()%3 == 1) f[p] = 1; //spielfeld fuellen
  nodes[startp].h = mincost(startp,goalp); nodes[startp].g = 1;
  nolist = 0; olist[nolist++] = startp;       //startknoten einragen
  do { pop_heap(olist,olist+nolist,ncomp); do_node(olist[--nolist]);
     } while(nolist && olist[0] != goalp);    //unten: weg markieren
  if(nolist) for(int q=olist[0]; q!=-1; q=nodes[q].prev)  f[q]=2;
  forint(t,0,maxp) cout << " #o."[f[t]] << (getx(t+1)?"":"\n");
}