From 5aafca6385908d9334a108c4a2e379eeddd28a7d Mon Sep 17 00:00:00 2001
From: Martin Mares <mj@ucw.cz>
Date: Sun, 2 Aug 2009 20:18:18 +0200
Subject: [PATCH] Resitko lodi.

---
 lode.c | 235 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 235 insertions(+)
 create mode 100644 lode.c

diff --git a/lode.c b/lode.c
new file mode 100644
index 0000000..8d1df45
--- /dev/null
+++ b/lode.c
@@ -0,0 +1,235 @@
+#include <stdio.h>
+
+#define N 13
+
+// Zadany planek: .=nevime, 0=nic, #<>^vo=kusy lodi
+static char map[N][N+1] = {
+    "0........>0..",
+    "...#.0......0",
+    "...0...0.....",
+    ".........0.0.",
+    "0.0..........",
+    "...#0.0......",
+    "........0...0",
+    ".0........0..",
+    "..0......0...",
+    "......0....0.",
+    ".....0.0....v",
+    "...0..>.0....",
+    ".0..0........",
+};
+
+// Zadane soucty: radky a sloupce
+static int sums[2][N] = {
+    { 4, 5, 1, 2, 2, 3, 1, 1, 5, 1, 3, 3, 4 },
+    { 2, 4, 1, 6, 2, 2, 4, 1, 1, 3, 3, 1, 5 },
+};
+
+// Zadane lode
+static int ships[] = {
+    5, 4, 4, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1,
+    -1
+};
+#define NSHIPS (int)(sizeof(ships) / sizeof(ships[0]) - 1)
+
+// Reseni
+static char sea[N][N+1];
+static int pos[NSHIPS][3];
+
+static void show(void)
+{
+#if 0
+  printf("    ");
+  for (int j=0; j<N; j++)
+    printf("%d", sums[1][j]);
+  putchar('\n');
+  for (int i=0; i<N; i++)
+    printf("%2d  %s  %s\n", sums[0][i], sea[i], map[i]);
+  for (int i=0; i<NSHIPS; i++)
+    printf("%d [%d] %d,%d,%d\n", i, ships[i], pos[i][0], pos[i][1], pos[i][2]);
+#else
+  for (int i=0; i<N; i++)
+    printf("%s\n", sea[i]);
+#endif
+  puts("");
+}
+
+// Cteni z more (dir=preklopeni, x=radek, y=sloupec)
+static int s(int dir, int x, int y)
+{
+  if (x < 0 || x >= N || y < 0 || y >= N)
+    return '.';
+  return dir ? sea[y][x] : sea[x][y];
+}
+
+// Cteni z mapy (dir=preklopeni, x=radek, y=sloupec)
+static int m(int dir, int x, int y)
+{
+  if (x < 0 || x >= N || y < 0 || y >= N)
+    return '.';
+  return dir ? map[y][x] : map[x][y];
+}
+
+// Zapis do more
+static void p(int dir, int x, int y, int ch)
+{
+  if (dir)
+    sea[y][x] = ch;
+  else
+    sea[x][y] = ch;
+}
+
+// Da se na pozici (dir,x,y) umistit lod delky len?
+static int check(int dir, int x, int y, int len)
+{
+  // Vodorovne pocitadlo
+  if (sums[dir][x] < len)
+    return 0;
+
+  // Svisla pocitadla
+  for (int yy = y; yy < y+len; yy++)
+    if (sums[!dir][yy] < 1)
+      return 0;
+
+  // Misto v mori (lod s okolim)
+  for (int xx = x-1; xx <= x+1; xx++)
+    for (int yy = y-1; yy <= y+len; yy++)
+      if (s(dir, xx, yy) != '.')
+	return 0;
+
+  // Misto na mape (jen lod sama)
+  if (len == 1)
+    {
+      if (m(dir, x, y) != '.' && m(dir, x, y) != 'o')
+	return 0;
+    }
+  else
+    {
+      if (m(dir, x, y) != '.' && m(dir, x, y) != "<^"[dir] ||
+	  m(dir, x, y+len-1) != '.' && m(dir, x, y+len-1) != ">v"[dir])
+	return 0;
+      for (int yy = y+1; yy < y+len-1; yy++)
+	if (m(dir, x, yy) != '.' && m(dir, x, yy) != '#')
+	  return 0;
+    }
+
+  return 1;
+}
+
+// Umisti na pozici (dir,x,y) lod delky len
+static void put(int dir, int x, int y, int len)
+{
+  sums[dir][x] -= len;
+
+  if (len == 1)
+    {
+      sums[!dir][y]--;
+      p(dir, x, y, 'o');
+      return;
+    }
+
+  for (int yy = y; yy < y+len; yy++)
+    {
+      sums[!dir][yy]--;
+      int ch;
+      if (yy == y)
+	ch = "<^"[dir];
+      else if (yy == y+len-1)
+	ch = ">v"[dir];
+      else
+	ch = "=|"[dir];
+      p(dir, x, yy, ch);
+    }
+}
+
+// Smaze z pozice (dir,x,y) lod delky len
+static void undo(int dir, int x, int y, int len)
+{
+  sums[dir][x] += len;
+
+  for (int yy = y; yy < y+len; yy++)
+    {
+      sums[!dir][yy]++;
+      p(dir, x, yy, '.');
+    }
+}
+
+// Porovna dve pozice lexikograficky
+static int posless(int *a, int *b)
+{
+  for (int i=0; i<3; i++)
+    if (a[i] < b[i])
+      return 1;
+    else if (a[i] > b[i])
+      return 0;
+  return 0;
+}
+
+// Zkontroluje, zda je more konsistentni s mapou
+static int consistent(void)
+{
+  for (int x=0; x<N; x++)
+    for (int y=0; y<N; y++)
+      {
+	int m = map[x][y];
+	int s = sea[x][y];
+	int ok;
+	switch (map[x][y])
+	  {
+	  case '#':
+	    ok = (s == '|' || s == '=');
+	    break;
+	  case '0':
+	    ok = (s == '.');
+	    break;
+	  case '.':
+	    ok = 1;
+	    break;
+	  default:
+	    ok = (s == m);
+	  }
+	if (!ok)
+	  return 0;
+      }
+  return 1;
+}
+
+static void place(int sh)
+{
+  if (ships[sh] < 0)
+    {
+      if (consistent())
+	show();
+      return;
+    }
+  int len = ships[sh];
+
+  int dirs = (len == 1 ? 1 : 2);
+  for (int dir = 0; dir < dirs; dir++)
+    for (int x = 0; x < N; x++)
+      for (int y = 0; y <= N - len; y++)
+	{
+	  pos[sh][0] = dir; pos[sh][1] = x; pos[sh][2] = y;
+	  if (sh && ships[sh-1] == len && posless(pos[sh], pos[sh-1]))
+	    continue;
+	  if (check(dir, x, y, len))
+	    {
+	      put(dir, x, y, len);
+	      place(sh+1);
+	      undo(dir, x, y, len);
+	    }
+	}
+}
+
+int main(void)
+{
+  for (int i=0; i<N; i++)
+    {
+      for (int j=0; j<N; j++)
+	sea[i][j] = '.';
+      sea[i][N] = 0;
+    }
+
+  place(0);
+  return 0;
+}
-- 
2.39.2