// go brettspiel in c++.                       // 2001 stefan reiss
#include <iostream>                            //      www.reisz.de
typedef int pos_t;
const int MAXX = 9 , MAXY = 9 , MAXP = MAXX * MAXY;
inline int   getx(pos_t p)     { return p % MAXX; }
inline int   gety(pos_t p)     { return p / MAXX; } 
inline pos_t getp(int x,int y) { return y * MAXX + x; } 
const int d4_off[] = { 1 , -MAXX, -1 , MAXX };
#define forint(i,a,b) for(int i=(a);i!=(b);++i)
#define FORNEIGHS(p,np) forint(d,0,4)\
  if(!(d==0&&getx(p)==MAXX-1) && !(d==2&&getx(p)==0))\
    if((np=(p)+d4_off[d]) >= 0  &&  np < MAXP)

// hat die kette ab p freiheiten ?; entfernt gegebenenfalls kette
bool has_libs (int * brd , pos_t p , bool remove_if_not)
{ static pos_t   v[MAXP];   // liste der positionen der kette
  static bool done[MAXP];   // flags, welche waren schon dran 
  int n,i,vsize = 0, pl = brd[p];  // vsize = anzahl in v
  v[vsize++] = p; done[p] = true;  // trage startstein ein
  for(i=0;i!=vsize;++i)            // fuer alle steine der kette
    FORNEIGHS(v[i],n)                     // fuer deren nachbarn
    { if (brd[n] == 0) goto haslibs;      // hat freiheit, fertig
      if (brd[n] == pl && !done[n])       // kette geht weiter
      { done[n] = true; v[vsize++] = n; } // eintrag fuer spaeter
    }
  if (remove_if_not) forint(k,0,vsize) brd[v[k]]=0; // entferne
 haslibs: 
  forint(k,0,vsize) done[v[k]]=false; // fuer naechsten aufruf
  return i!=vsize;
}

// setzt zug auf pos, wenn erlaubt. return , ob zug erlaubt
bool do_move (int * brd , pos_t pos , int pl)
{ if (brd[pos]!=0) return false;    // ist schon belegt
  brd[pos] = pl;                    // setze stein
  pos_t n; FORNEIGHS(pos,n)         // pruefe ob ich gegner fange
  { if (brd[n] == (pl^3)) has_libs (brd , n , true); }
  if (!has_libs(brd , pos , false)) // falls ich gefangen waere ...
  { brd[pos] = 0; return false; }   // nimm zurueck + return false
  return true;
}

int board[MAXP]; int currpl = 1; char line[10]; void rmv();
void main()
{ using namespace std;
  cout << "x=ende;<xy>=zug;c=clear;^=wechsel;s<xyp>=setze feld;\n";
  for(;line[0]!='x';)
  { forint(p,0,MAXP) cout << ".*o"[board[p]] << (getx(p+1)?"":"\n");
    cout << ".*o"[currpl] << "\n"; // ^ausgabe der stellung + currpl
    cin >> line;
    if (line[0]>='0' && line[0]<'0'+MAXX)
      if (do_move(board,getp(line[0]-'0',line[1]-'0'),currpl))
        currpl^=3; else cout << "verboten\a\n";
    if (line[0]=='s') board[getp(line[1]-'0',line[2]-'0')]=line[3]-'0';
    if (line[0]=='^') currpl ^=3;
    if (line[0]=='c') forint(i,0,MAXP) board[i]=0;
    if (line[0]=='r') forint(i,0,MAXP*3) { rmv(); currpl^=3; }
  }                                     //^rmv = zufallszuege
}

void rmv(){int i=0,n,p,p0=rand()%MAXP;for(;p=(p0+i)%MAXP,i<MAXP;++i)
 FORNEIGHS(p,n)if(board[n]!=currpl&&do_move(board,p,currpl))return;}