lode.c

   1 #include <stdio.h>
   2
   3 #define N 13
   4
   5 // Zadany planek: .=nevime, 0=nic, #<>^vo=kusy lodi
   6 static char map[N][N+1] = {
   7     "0........>0..",
   8     "...#.0......0",
   9     "...0...0.....",
  10     ".........0.0.",
  11     "0.0..........",
  12     "...#0.0......",
  13     "........0...0",
  14     ".0........0..",
  15     "..0......0...",
  16     "......0....0.",
  17     ".....0.0....v",
  18     "...0..>.0....",
  19     ".0..0........",
  20 };
  21
  22 // Zadane soucty: radky a sloupce
  23 static int sums[2][N] = {
  24     { 4, 5, 1, 2, 2, 3, 1, 1, 5, 1, 3, 3, 4 },
  25     { 2, 4, 1, 6, 2, 2, 4, 1, 1, 3, 3, 1, 5 },
  26 };
  27
  28 // Zadane lode
  29 static int ships[] = {
  30     5, 4, 4, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1,
  31     -1
  32 };
  33 #define NSHIPS (int)(sizeof(ships) / sizeof(ships[0]) - 1)
  34
  35 // Reseni
  36 static char sea[N][N+1];
  37 static int pos[NSHIPS][3];
  38
  39 static void show(void)
  40 {
  41 #if 0
  42   printf("    ");
  43   for (int j=0; j<N; j++)
  44     printf("%d", sums[1][j]);
  45   putchar('\n');
  46   for (int i=0; i<N; i++)
  47     printf("%2d  %s  %s\n", sums[0][i], sea[i], map[i]);
  48   for (int i=0; i<NSHIPS; i++)
  49     printf("%d [%d] %d,%d,%d\n", i, ships[i], pos[i][0], pos[i][1], pos[i][2]);
  50 #else
  51   for (int i=0; i<N; i++)
  52     printf("%s\n", sea[i]);
  53 #endif
  54   puts("");
  55 }
  56
  57 // Cteni z more (dir=preklopeni, x=radek, y=sloupec)
  58 static int s(int dir, int x, int y)
  59 {
  60   if (x < 0 || x >= N || y < 0 || y >= N)
  61     return '.';
  62   return dir ? sea[y][x] : sea[x][y];
  63 }
  64
  65 // Cteni z mapy (dir=preklopeni, x=radek, y=sloupec)
  66 static int m(int dir, int x, int y)
  67 {
  68   if (x < 0 || x >= N || y < 0 || y >= N)
  69     return '.';
  70   return dir ? map[y][x] : map[x][y];
  71 }
  72
  73 // Zapis do more
  74 static void p(int dir, int x, int y, int ch)
  75 {
  76   if (dir)
  77     sea[y][x] = ch;
  78   else
  79     sea[x][y] = ch;
  80 }
  81
  82 // Da se na pozici (dir,x,y) umistit lod delky len?
  83 static int check(int dir, int x, int y, int len)
  84 {
  85   // Vodorovne pocitadlo
  86   if (sums[dir][x] < len)
  87     return 0;
  88
  89   // Svisla pocitadla
  90   for (int yy = y; yy < y+len; yy++)
  91     if (sums[!dir][yy] < 1)
  92       return 0;
  93
  94   // Misto v mori (lod s okolim)
  95   for (int xx = x-1; xx <= x+1; xx++)
  96     for (int yy = y-1; yy <= y+len; yy++)
  97       if (s(dir, xx, yy) != '.')
  98         return 0;
  99
 100   // Misto na mape (jen lod sama)
 101   if (len == 1)
 102     {
 103       if (m(dir, x, y) != '.' && m(dir, x, y) != 'o')
 104         return 0;
 105     }
 106   else
 107     {
 108       if (m(dir, x, y) != '.' && m(dir, x, y) != "<^"[dir] ||
 109           m(dir, x, y+len-1) != '.' && m(dir, x, y+len-1) != ">v"[dir])
 110         return 0;
 111       for (int yy = y+1; yy < y+len-1; yy++)
 112         if (m(dir, x, yy) != '.' && m(dir, x, yy) != '#')
 113           return 0;
 114     }
 115
 116   return 1;
 117 }
 118
 119 // Umisti na pozici (dir,x,y) lod delky len
 120 static void put(int dir, int x, int y, int len)
 121 {
 122   sums[dir][x] -= len;
 123
 124   if (len == 1)
 125     {
 126       sums[!dir][y]--;
 127       p(dir, x, y, 'o');
 128       return;
 129     }
 130
 131   for (int yy = y; yy < y+len; yy++)
 132     {
 133       sums[!dir][yy]--;
 134       int ch;
 135       if (yy == y)
 136         ch = "<^"[dir];
 137       else if (yy == y+len-1)
 138         ch = ">v"[dir];
 139       else
 140         ch = "=|"[dir];
 141       p(dir, x, yy, ch);
 142     }
 143 }
 144
 145 // Smaze z pozice (dir,x,y) lod delky len
 146 static void undo(int dir, int x, int y, int len)
 147 {
 148   sums[dir][x] += len;
 149
 150   for (int yy = y; yy < y+len; yy++)
 151     {
 152       sums[!dir][yy]++;
 153       p(dir, x, yy, '.');
 154     }
 155 }
 156
 157 // Porovna dve pozice lexikograficky
 158 static int posless(int *a, int *b)
 159 {
 160   for (int i=0; i<3; i++)
 161     if (a[i] < b[i])
 162       return 1;
 163     else if (a[i] > b[i])
 164       return 0;
 165   return 0;
 166 }
 167
 168 // Zkontroluje, zda je more konsistentni s mapou
 169 static int consistent(void)
 170 {
 171   for (int x=0; x<N; x++)
 172     for (int y=0; y<N; y++)
 173       {
 174         int m = map[x][y];
 175         int s = sea[x][y];
 176         int ok;
 177         switch (map[x][y])
 178           {
 179           case '#':
 180             ok = (s == '|' || s == '=');
 181             break;
 182           case '0':
 183             ok = (s == '.');
 184             break;
 185           case '.':
 186             ok = 1;
 187             break;
 188           default:
 189             ok = (s == m);
 190           }
 191         if (!ok)
 192           return 0;
 193       }
 194   return 1;
 195 }
 196
 197 static void place(int sh)
 198 {
 199   if (ships[sh] < 0)
 200     {
 201       if (consistent())
 202         show();
 203       return;
 204     }
 205   int len = ships[sh];
 206
 207   int dirs = (len == 1 ? 1 : 2);
 208   for (int dir = 0; dir < dirs; dir++)
 209     for (int x = 0; x < N; x++)
 210       for (int y = 0; y <= N - len; y++)
 211         {
 212           pos[sh][0] = dir; pos[sh][1] = x; pos[sh][2] = y;
 213           if (sh && ships[sh-1] == len && posless(pos[sh], pos[sh-1]))
 214             continue;
 215           if (check(dir, x, y, len))
 216             {
 217               put(dir, x, y, len);
 218               place(sh+1);
 219               undo(dir, x, y, len);
 220             }
 221         }
 222 }
 223
 224 int main(void)
 225 {
 226   for (int i=0; i<N; i++)
 227     {
 228       for (int j=0; j<N; j++)
 229         sea[i][j] = '.';
 230       sea[i][N] = 0;
 231     }
 232
 233   place(0);
 234   return 0;
 235 }