+enum {
+ ERR_ADJ_TOPLEFT = 4,
+ ERR_ADJ_TOP,
+ ERR_ADJ_TOPRIGHT,
+ ERR_ADJ_LEFT,
+ ERR_ADJ_RIGHT,
+ ERR_ADJ_BOTLEFT,
+ ERR_ADJ_BOT,
+ ERR_ADJ_BOTRIGHT,
+ ERR_OVERCOMMITTED
+};
+
+static int *find_errors(game_state *state)
+{
+ int w = state->p.w, h = state->p.h;
+ int *ret = snewn(w*h + w + h, int);
+ int *tmp = snewn(w*h*2, int), *dsf = tmp + w*h;
+ int x, y;
+
+ /*
+ * ret[0] through to ret[w*h-1] give error markers for the grid
+ * squares. After that, ret[w*h] to ret[w*h+w-1] give error
+ * markers for the column numbers, and ret[w*h+w] to
+ * ret[w*h+w+h-1] for the row numbers.
+ */
+
+ /*
+ * Spot tent-adjacency violations.
+ */
+ for (x = 0; x < w*h; x++)
+ ret[x] = 0;
+ for (y = 0; y < h; y++) {
+ for (x = 0; x < w; x++) {
+ if (y+1 < h && x+1 < w &&
+ ((state->grid[y*w+x] == TENT &&
+ state->grid[(y+1)*w+(x+1)] == TENT) ||
+ (state->grid[(y+1)*w+x] == TENT &&
+ state->grid[y*w+(x+1)] == TENT))) {
+ ret[y*w+x] |= 1 << ERR_ADJ_BOTRIGHT;
+ ret[(y+1)*w+x] |= 1 << ERR_ADJ_TOPRIGHT;
+ ret[y*w+(x+1)] |= 1 << ERR_ADJ_BOTLEFT;
+ ret[(y+1)*w+(x+1)] |= 1 << ERR_ADJ_TOPLEFT;
+ }
+ if (y+1 < h &&
+ state->grid[y*w+x] == TENT &&
+ state->grid[(y+1)*w+x] == TENT) {
+ ret[y*w+x] |= 1 << ERR_ADJ_BOT;
+ ret[(y+1)*w+x] |= 1 << ERR_ADJ_TOP;
+ }
+ if (x+1 < w &&
+ state->grid[y*w+x] == TENT &&
+ state->grid[y*w+(x+1)] == TENT) {
+ ret[y*w+x] |= 1 << ERR_ADJ_RIGHT;
+ ret[y*w+(x+1)] |= 1 << ERR_ADJ_LEFT;
+ }
+ }
+ }
+
+ /*
+ * Spot numeric clue violations.
+ */
+ for (x = 0; x < w; x++) {
+ int tents = 0, maybetents = 0;
+ for (y = 0; y < h; y++) {
+ if (state->grid[y*w+x] == TENT)
+ tents++;
+ else if (state->grid[y*w+x] == BLANK)
+ maybetents++;
+ }
+ ret[w*h+x] = (tents > state->numbers->numbers[x] ||
+ tents + maybetents < state->numbers->numbers[x]);
+ }
+ for (y = 0; y < h; y++) {
+ int tents = 0, maybetents = 0;
+ for (x = 0; x < w; x++) {
+ if (state->grid[y*w+x] == TENT)
+ tents++;
+ else if (state->grid[y*w+x] == BLANK)
+ maybetents++;
+ }
+ ret[w*h+w+y] = (tents > state->numbers->numbers[w+y] ||
+ tents + maybetents < state->numbers->numbers[w+y]);
+ }
+
+ /*
+ * Identify groups of tents with too few trees between them,
+ * which we do by constructing the connected components of the
+ * bipartite adjacency graph between tents and trees
+ * ('bipartite' in the sense that we deliberately ignore
+ * adjacency between tents or between trees), and highlighting
+ * all the tents in any component which has a smaller tree
+ * count.
+ */
+ dsf_init(dsf, w*h);
+ /* Construct the equivalence classes. */
+ for (y = 0; y < h; y++) {
+ for (x = 0; x < w-1; x++) {
+ if ((state->grid[y*w+x]==TREE && state->grid[y*w+x+1]==TENT) ||
+ (state->grid[y*w+x]==TENT && state->grid[y*w+x+1]==TREE))
+ dsf_merge(dsf, y*w+x, y*w+x+1);
+ }
+ }
+ for (y = 0; y < h-1; y++) {
+ for (x = 0; x < w; x++) {
+ if ((state->grid[y*w+x]==TREE && state->grid[(y+1)*w+x]==TENT) ||
+ (state->grid[y*w+x]==TENT && state->grid[(y+1)*w+x]==TREE))
+ dsf_merge(dsf, y*w+x, (y+1)*w+x);
+ }
+ }
+ /* Count up the tent/tree difference in each one. */
+ for (x = 0; x < w*h; x++)
+ tmp[x] = 0;
+ for (x = 0; x < w*h; x++) {
+ y = dsf_canonify(dsf, x);
+ if (state->grid[x] == TREE)
+ tmp[y]++;
+ else if (state->grid[x] == TENT)
+ tmp[y]--;
+ }
+ /* And highlight any tent belonging to an equivalence class with
+ * a score less than zero. */
+ for (x = 0; x < w*h; x++) {
+ y = dsf_canonify(dsf, x);
+ if (state->grid[x] == TENT && tmp[y] < 0)
+ ret[x] |= 1 << ERR_OVERCOMMITTED;
+ }
+
+ /*
+ * Identify groups of trees with too few tents between them.
+ * This is done similarly, except that we now count BLANK as
+ * equivalent to TENT, i.e. we only highlight such trees when
+ * the user hasn't even left _room_ to provide tents for them
+ * all. (Otherwise, we'd highlight all trees red right at the
+ * start of the game, before the user had done anything wrong!)
+ */
+#define TENT(x) ((x)==TENT || (x)==BLANK)
+ dsf_init(dsf, w*h);
+ /* Construct the equivalence classes. */
+ for (y = 0; y < h; y++) {
+ for (x = 0; x < w-1; x++) {
+ if ((state->grid[y*w+x]==TREE && TENT(state->grid[y*w+x+1])) ||
+ (TENT(state->grid[y*w+x]) && state->grid[y*w+x+1]==TREE))
+ dsf_merge(dsf, y*w+x, y*w+x+1);
+ }
+ }
+ for (y = 0; y < h-1; y++) {
+ for (x = 0; x < w; x++) {
+ if ((state->grid[y*w+x]==TREE && TENT(state->grid[(y+1)*w+x])) ||
+ (TENT(state->grid[y*w+x]) && state->grid[(y+1)*w+x]==TREE))
+ dsf_merge(dsf, y*w+x, (y+1)*w+x);
+ }
+ }
+ /* Count up the tent/tree difference in each one. */
+ for (x = 0; x < w*h; x++)
+ tmp[x] = 0;
+ for (x = 0; x < w*h; x++) {
+ y = dsf_canonify(dsf, x);
+ if (state->grid[x] == TREE)
+ tmp[y]++;
+ else if (TENT(state->grid[x]))
+ tmp[y]--;
+ }
+ /* And highlight any tree belonging to an equivalence class with
+ * a score more than zero. */
+ for (x = 0; x < w*h; x++) {
+ y = dsf_canonify(dsf, x);
+ if (state->grid[x] == TREE && tmp[y] > 0)
+ ret[x] |= 1 << ERR_OVERCOMMITTED;
+ }
+#undef TENT
+
+ sfree(tmp);
+ return ret;
+}
+
+static void draw_err_adj(drawing *dr, game_drawstate *ds, int x, int y)
+{
+ int coords[8];
+ int yext, xext;
+
+ /*
+ * Draw a diamond.
+ */
+ coords[0] = x - TILESIZE*2/5;
+ coords[1] = y;
+ coords[2] = x;
+ coords[3] = y - TILESIZE*2/5;
+ coords[4] = x + TILESIZE*2/5;
+ coords[5] = y;
+ coords[6] = x;
+ coords[7] = y + TILESIZE*2/5;
+ draw_polygon(dr, coords, 4, COL_ERROR, COL_GRID);
+
+ /*
+ * Draw an exclamation mark in the diamond. This turns out to
+ * look unpleasantly off-centre if done via draw_text, so I do
+ * it by hand on the basis that exclamation marks aren't that
+ * difficult to draw...
+ */
+ xext = TILESIZE/16;
+ yext = TILESIZE*2/5 - (xext*2+2);
+ draw_rect(dr, x-xext, y-yext, xext*2+1, yext*2+1 - (xext*3),
+ COL_ERRTEXT);
+ draw_rect(dr, x-xext, y+yext-xext*2+1, xext*2+1, xext*2, COL_ERRTEXT);
+}
+