#include <cassert>
#include <cstdio>
#include <string>
#include <map>
#include <iostream>

//!!!!!!!!!!!!
#define PROBLEM_NAME "snakes2"
#define TEST_STR "%03d"
#include "gentools.h"

#ifdef DEBUG
#define eprintf(...) fprintf (stderr, __VA_ARGS__)
#else
#define eprintf(...) assert (true)
#endif

using namespace std;

const int MINn = 1, MAXn = 7;
const int MINk = 1, MAXk = 3;
const int MINm = 2, MAXm = 25;
const int MINc = 1, MAXc = MAXm;
const int MINlen = 4, MAXlen = MAXm * MAXm;

int m, k;
char malachite[MAXm][MAXm][10]; 
int snakes[MAXk][MAXlen + 1][2];
string snake_intersections[MAXk];
int len[MAXk];
int S[MAXm][MAXm];

void close_test()
{
}

void log_test()
{
 fprintf (flog, "m = %d, k = %d", m, k);
}

void test_coordinates(int x1, int y1, int x2, int y2)
{
  if(x2 - x1 == 0)
    assert((y2 - y1 == 1) || (y2 - y1 == -1));
  else if(y2 - y1 == 0)
    assert((x2 - x1 == 1) || (x2 - x1 == -1));
  else
    assert(0);
}

void verify_test()
{
 // check global constraints

  assert (MINm <= m && m <= MAXm);
 // assert (MINn <= n && n <= MAXn);
  assert (MINk <= k && k <= MAXk);

 int i, j;
 // check coordinates
 for (i = 0; i < k; i++)
 {
  assert (MINlen <= len[i] && len[i] <= MAXlen);
  for (j = 0; j < len[i]; j++)
  {
   assert (1 <= snakes[i][j][0] && snakes[i][j][0] <= m);
   assert (1 <= snakes[i][j][1] && snakes[i][j][1] <= m);
  }
 }

  for(i = 0; i < m; i++)
    for(j = 0; j < m; j++)
      S[i][j] = 0;
  for(i = 0; i < k; i++)
    for(j = 0; j < len[i]; j++)
      S[snakes[i][j][0]-1][snakes[i][j][1]-1]++;


  for(i = 0; i < m; i++)
    for(j = 0; j < m; j++)
      assert(S[i][j] <= 2);
  
  // check paths
  for(i = 0; i < k; i++)
    for(j = 0; j < len[i]; j++)
      test_coordinates(snakes[i][j][0], snakes[i][j][1], snakes[i][(j + 1)%len[i]][0], snakes[i][(j + 1)%len[i]][1]);

  int n = 0;
  for(i = 0; i < MAXm; i++)
    for(j = 0; j < MAXm; j++)
      if(S[i][j] == 2)
        n++;
  assert(MINn <= n && n <= MAXn);
}

void open_test()
{
 m = MINm - 1;
 k = 0;
}

void shuffle_test()
{
}

void output_test(void)
{
 FILE * fout;

 fout = fopen (cur_test_str, "wt");
 assert (fout != NULL);

 int i, j;
 
 fprintf(fout, "%d\n", k);
 for (i = 0; i < k; i++)
 {
   fprintf(fout, "%d ", len[i]);
   
   for (j = 0; j < len[i]; j++)
     fprintf (fout, "%d %d%c", snakes[i][j][0] + 1, snakes[i][j][1] + 1,
              j + 1 < len[i] ? ' ' : '\n');
//   fprintf(fout, "%s\n", snake_intersections[i].c_str());
 }
 fclose (fout);
}

void read_number(int y_num, int x_num, char* p_ch, int* p_number)
{
  if(k == 1)
    sscanf(malachite[y_num][x_num], "%d", p_number);
  else
    sscanf(malachite[y_num][x_num], "%c%d", p_ch, p_number);
}

bool check_simple_step(int next_num, int x1, int y1, int &x2, int &y2, int dx, int dy, int snake_number)
{
  if(malachite[y1 + dy][x1 + dx][0] == '*')
    return false;
  int number;
  char ch;
  read_number(y1 + dy, x1 + dx, &ch, &number);
  if(k != 1)
  {
    assert(ch >= 'a');
    assert(ch <= 'a' + k - 1);
    if(ch - 'a' + 1 != snake_number)
      return false;
  }
  if(number != next_num)
    return false;
  if(next_num != 1)
  {
    if(!(dx & 1))
      dx /= 2;
    if(!(dy & 1))
      dy /= 2;
    x2 = x1 + dx;
    y2 = y1 + dy;
  }
  return true;
}

bool get_next_point(int num, int x1, int y1, int &x2, int &y2, bool &tail, int snake_number = 0)
{
  // Простой случай
  if(check_simple_step(num + 1, x1, y1, x2, y2,  1,  0, snake_number)
   ||check_simple_step(num + 1, x1, y1, x2, y2, -1,  0, snake_number)
   ||check_simple_step(num + 1, x1, y1, x2, y2,  0,  1, snake_number)
   ||check_simple_step(num + 1, x1, y1, x2, y2,  0, -1, snake_number))
    return true;
  // Точка пересечения
  if(check_simple_step(num + 2, x1, y1, x2, y2,  2,  0, snake_number)
   ||check_simple_step(num + 2, x1, y1, x2, y2, -2,  0, snake_number)
   ||check_simple_step(num + 2, x1, y1, x2, y2,  0,  2, snake_number)
   ||check_simple_step(num + 2, x1, y1, x2, y2,  0, -2, snake_number))
    return true;
  // Хвост змейки
  if(check_simple_step(1, x1, y1, x2, y2,  1, 0, snake_number)
   ||check_simple_step(1, x1, y1, x2, y2, -1, 0, snake_number)
   ||check_simple_step(1, x1, y1, x2, y2,  1, 0, snake_number)
   ||check_simple_step(1, x1, y1, x2, y2, -1, 0, snake_number))
  {
    tail = true;
    return true;
  }
  return false;
}

void gen_manual_test(char* filename)
{
  string name = filename;
  START_TEST ("manual from file %s", filename);
  FILE* fin;

  fin = fopen (filename, "rt");
  assert (fin != NULL);

  fscanf(fin, "%d %d", &m, &k);
  int i, j, number;
  char ch;
  bool tail;
  map <pair<int, int>, int> snake_points;
  
  for(i = 0; i < k; i++)
  {
    fscanf(fin, "%d %d %d", &len[i], &snakes[i][0][0], &snakes[i][0][1]);
    snakes[i][0][0]--;
    snakes[i][0][1]--;
  }
  for(i = 0; i < m; i++)
    for(j = 0; j < m; j++)
      fscanf(fin, "%s", malachite[i][j]);
  
  // Записываем змееек в виде последовательности точек
  for(i = 0; i < k; i++)
  {
    // Check snake head
    //assert(malachite[snakes[i][0][1]][snakes[i][0][0]][0] != '*');
    assert(malachite[snakes[i][0][1]][snakes[i][0][0]] != "*");
    read_number(snakes[i][0][1], snakes[i][0][0], &ch, &number);
    if(k != 1)
      assert(ch == 'a' + i);
    assert(number == 1);
    tail = false;
    for(j = 0; j < len[i]; j++)
    {  
      if(k == 1)
        get_next_point(j + 1, snakes[i][j][0],   snakes[i][j][1], 
                              snakes[i][j+1][0], snakes[i][j+1][1], tail);
      else
        get_next_point(j + 1, snakes[i][j][0],   snakes[i][j][1], 
                              snakes[i][j+1][0], snakes[i][j+1][1], tail, i + 1);
    }
    assert(j == len[i]); // Правильная длина
  }
  
  // В snake_points записываем перекрестки
  for(i = 0; i < k; i++)
  {
    for(j = 0; j < len[i]; j++)
    {
      if(snake_points.find(make_pair(snakes[i][j][0], snakes[i][j][1])) == snake_points.end()) 
        snake_points[make_pair(snakes[i][j][0], snakes[i][j][1])] = 1;
      else
        snake_points[make_pair(snakes[i][j][0], snakes[i][j][1])]++;
    }
  } 
//  for(map <pair<int, int>, int>::iterator ittemp = snake_points.begin(); ittemp != snake_points.end(); ittemp++)
//    cout << "?" << ittemp->first.first << " " << ittemp->first.second << " " << ittemp->second;
  
  // Записываем плюсы и минусы
  for(i = 0; i < k; i++)
  {
    snake_intersections[i] = "";
    for(j = 0; j < len[i]; j++)
      if(snake_points[make_pair(snakes[i][j][0], snakes[i][j][1])] == 2)
      {
        assert(malachite[snakes[i][j][1]][snakes[i][j][0]] != "*");
        //assert(malachite[snakes[i][j][1]][snakes[i][j][0]] != '*');
        read_number(snakes[i][j][1], snakes[i][j][0], &ch, &number);
        if(k == 1)
        {
          if(number == j + 1)
            snake_intersections[i] += '+';
          else
            snake_intersections[i] += '-';
        }
        else
        {
          if(number == j + 1 && ch == 'a' + i)
            snake_intersections[i] += '+';
          else
            snake_intersections[i] += '-';
        }
      }
    // Проверка, что больше 2 раз не проходим
    for(j = 0; j < len[i]; j++)
      if(snake_points[make_pair(snakes[i][j][0], snakes[i][j][1])] > 2)
      {
        cout << "Snake " << i << " (and another snake) meet point (" << snakes[i][j][0] + 1 << "," << snakes[i][j][1] + 1 << ") more then 2 times" << "j=" << j << "\n";
        assert(0);
      }
  }
  fclose (fin);
  END_TEST ();
}

void gen_samples (void)
{
  // 4_1 в книге Мурасаги (зеркален)
  gen_manual_test("links/Mur_knot_4_1/Mur_knot_4_1.txt");

  gen_manual_test("links/Link_4a1/Link_4a1.txt");
}

void gen_manual()
{
  // 3_1 в книге Мурасаги Левый трилистник
  gen_manual_test("links/Mur_knot_3_1/Mur_knot_3_1.txt");

  // 5_1 в книге Прасолова и в Мурасаги тоже 
  gen_manual_test("links/Mur_knot_5_1/Mur_knot_5_1.txt");

  // 5_2 в книге Мурасаги 
  gen_manual_test("links/Mur_knot_5_2/Mur_knot_5_2.txt");

  // 6_1 в книге Мурасаги 
  gen_manual_test("links/Mur_knot_6_1/Mur_knot_6_1.txt");

  // 6_2 в книге Мурасаги 
  gen_manual_test("links/Mur_knot_6_2/Mur_knot_6_2.txt");

  // 6_3 в книге Мурасаги 
  gen_manual_test("links/Mur_knot_6_3/Mur_knot_6_3.txt");

  // 7_1 в книге Мурасаги 
  gen_manual_test("links/Mur_knot_7_1/Mur_knot_7_1.txt");

  // 7_2 в книге Мурасаги 
  gen_manual_test("links/Mur_knot_7_2/Mur_knot_7_2.txt");

  // 7_3 в книге Мурасаги 
  gen_manual_test("links/Mur_knot_7_3/Mur_knot_7_3.txt");

  // 7_4 в книге Мурасаги 
  gen_manual_test("links/Mur_knot_7_4/Mur_knot_7_4.txt");

  // 7_5 в книге Мурасаги 
  gen_manual_test("links/Mur_knot_7_5/Mur_knot_7_5.txt");

  // 7_6 в книге Мурасаги 
  gen_manual_test("links/Mur_knot_7_6/Mur_knot_7_6.txt");

  // 7_7 в книге Мурасаги 
  gen_manual_test("links/Mur_knot_7_7/Mur_knot_7_7.txt");


  
  
  // 3_1 в книге Прасолова Правый трилистник
  gen_manual_test("links/Pr_knot_3_1/knot_3_1.txt");

  // 4_1 в книге Прасолова Восьмерка
  gen_manual_test("links/Pr_knot_4_1/knot_4_1.txt");

  // 5_1 в книге Прасолова и в Мурасаги тоже 
  gen_manual_test("links/Pr_knot_5_1/knot_5_1.txt");


  
  gen_manual_test("links/Pr_comp_knot1/Pr_composite_knot1.txt");
  gen_manual_test("links/Pr_comp_knot2/Pr_composite_knot2.txt");


  
  gen_manual_test("links/Link_2a1/Link_2a1.txt");
  gen_manual_test("links/Link_5a1/Link_5a1.txt");
  gen_manual_test("links/Link_6a1/Link_6a1.txt");
  gen_manual_test("links/Link_6a2/Link_6a2.txt");
  gen_manual_test("links/Link_6a4/Link_6a4.txt");

  gen_manual_test("links/TrivialLink1/TrivialLink1.txt");
  gen_manual_test("links/TrivialLink2/TrivialLink2.txt");
}

int main(int argc, char* argv[])
{
  init_gen(argc, argv);

  gen_samples();

  gen_manual();

  exit_gen();

  return 0;
}
