/* Problem 4--Minesweeper
   This problem was excruciatingly difficult.  I imagine they wanted to
   severely reduce the number of teams receiving perfect scores.  Two
   teams did manage to get all 8 problems.  Those two teams were the
   only two to correctly complete Minesweeper.
   There are several ways to attempt this problem.  However, none of
   them eliminate the need for some sort of trial-and-error guessing
   routine.  I did it by setting and solving a system of linear
   equations:  an equation is generated for each entry whose value is
   known.  Some variables get solved using this approach, and their
   fixed value is recorded.  Some variables drop completely out of the
   system of equations, so they are known to be ambiguous.  However,
   what is left are a set of variables that depend upon each other.  It
   is not correct to assume that these are all ambiguous because the
   fact that each variable is constrained to be 0 or 1 sometimes will
   uniquely specify one or more of these variables.  It was at this
   point that I used trial-and-error.  I could have analyzed it even
   more to decrease the amount of guesswork, but this code is long
   enough as it is. */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))

typedef struct point { /* This holds information relevant to a */
 int i,j,v,p,n;        /* it's coordinate in the matrix, test values */
} point;               /* and the possibilities of mine possession. */

typedef struct dept {  /* A dependent variable contains a pointer to */
 int v, eqn;           /* the list of variables and a pointer to the */
} dept;                /* equation that defined it. */

int main (int argc, char **argv);
void Initialize (void);
void BuildEquations (void);
int VarsPresent (int i, int j);
void AddEq (int i, int j);
void ge (void);
int LastZero (void);
void Separate (void);
int ValidDep (void);
int AdvanceInd (void);
void UpdateDepInt (void);
void TrialandError (void);
void EvaluateDep (void);
void PrintResult (void);

FILE *in, *out; /* input matrix, variable pointer, list of indep vars*/
int r,c, M[10][10], V[10][10], vars, I[100];
point P[100]; /* list of variables */
int EQ[100][101]; int eqct, dct, ict; /* matrix for equation info */
dept D[100]; /* list of dependent variables */

int main (int argc, char **argv) {

 in = fopen ("prob4.in","r");
 out = fopen ("prob4.out","w");
 while (1) {
  fscanf (in,"%d %d",&r,&c);
  if (r==0 && c==0) break;
  Initialize ();
  BuildEquations ();
  ge ();
  Separate ();
  TrialandError ();
  PrintResult ();
 }
 fclose (in);
 fclose (out);
 return EXIT_SUCCESS;
}

/* Initialize reads in the next data set and initializes the appropriate
   data structures. */
void Initialize (void) {

  int i, j;

 vars=0;
 for (i = 0; i < r; i++)
  for (j = 0; j < c; j++) {
   fscanf (in,"%d",&M[i][j]);
   if (M[i][j]==-1) { /* read in a variable */
    P[vars].i = i; P[vars].j = j;
    P[vars].p = P[vars].n = 1; /* add to variable list */
    P[vars].v = 0;
    vars++;
    V[i][j] = vars; /* pointer to entry in variable list */
   }
   else V[i][j] = 0;
  }
  memset (EQ,0,sizeof EQ);
  eqct = 0;
}

/* This builds the equation matrix.  If an entry corresponds to an
   equation, it is added. */

void BuildEquations (void) {

  int i, j;

 for (i=0; i < r; i++)
  for (j=0; j < c; j++)
   if (VarsPresent (i,j)) AddEq (i,j);
}

/* This decides whether an entry corresponds to an equation. */
int VarsPresent (int i, int j) {

  int ii, jj;

 if (M[i][j]==-1) return 0; /* Entry can't be a variable */
 for (ii = MAX (0,i-1); ii <= MIN (r-1,i+1); ii++)
  for (jj = MAX (0,j-1); jj <= MIN (c-1,j+1); jj++)
   if (M[ii][jj]==-1) return 1; /* and there must be at least one */
 return 0;                      /* variable adjacent to it. */
}

/* This adds an equation to the equation matrix. */
void AddEq (int i, int j) {

  int ii, jj;

 for (ii = MAX (0,i-1); ii <= MIN (r-1,i+1); ii++)
  for (jj = MAX (0,j-1); jj <= MIN (c-1,j+1); jj++)
   if (ii==i && jj==j)
    EQ[eqct][vars] = M[i][j]; /* add the constant term */
   else
    if (V[ii][jj]) EQ[eqct][V[ii][jj]-1] = 1; /* add variable */
 eqct++;
}

/* This performs Gaussian Elimination to solve the system of equations*/
void ge (void) {

  int r,c,maxr,row,col, max, T;

 for (r=c=0;r < eqct && c <= vars;c++) {
  max = abs (EQ[r][c]);
  maxr = r;
  for (row = r+1;row < eqct;row++)
   if (abs (EQ[row][c]) > max) {
    max = abs (EQ[row][c]);
    maxr = row;
   }
  if (max > 0) {
   for (col = c;col <= vars;col++) {
    T = EQ[r][col];
    EQ[r][col] = EQ[maxr][col];
    EQ[maxr][col] = T;
   }
   for (col = c+1;col <= vars;col++)
    EQ[r][col] = EQ[r][col] / EQ[r][c];
   EQ[r][c] = 1;
   for (row = 0;row < eqct;row++) {
    if (row==r) continue;
    for (col=c+1;col<=vars;col++)
     EQ[row][col] -= EQ[row][c] * EQ[r][col];
    EQ[row][c]=0;
   }
   r++;
  }
 }
 while (eqct > 0 && LastZero()) eqct--; /* Kill all zero rows */
}

/* This checks whether the last row of the equation matrix is all
   zeros. */
int LastZero (void) {

  int j;

 for (j=0; j <= vars; j++)
  if (EQ[eqct-1][j] != 0)
   return 0;
 return 1;
}

/* Separate divides the variables into solved, cancelled, dependent,
   and independent variables. */
void Separate (void) {

  int i, j, jj, dep, T[100]={0};

 ict = dct = 0;
 for (i=0; i < eqct; i++) {
  for (j=0; EQ[i][j]==0;j++);
  dep =0;
  for (jj=j+1;jj<vars;jj++)
   if (EQ[i][jj]!=0) T[jj] = dep = 1; /* This is an independent var. */
  if (dep) {/* This is a dependent var; add it to list. */
   D[dct].v = j;
   D[dct++].eqn = i;
  } else
   if (EQ[i][vars]!=0) P[j].n = 0; /* This is solved.  Set its solved */
   else P[j].p = 0;                /* value. */
 }
 for (i=0; i < vars; i++)
  if (T[i]) I[ict++] = i; /* Make list of independent vars. */
 for (i=0; i < ict; i++) /* Initialize info for dep and ind vars. */
  P[I[i]].p = P[I[i]].n = 0;
 for (i=0; i < dct; i++)
  P[D[i].v].p = P[D[i].v].n = 0;
}

/* This checks whether the dependent variables have a valid assignment;
   that is, they must each be 0 or 1. */
int ValidDep (void) {

  int i;

 for (i=0;i<dct;i++)
  if (P[D[i].v].v != 0 && P[D[i].v].v != 1)
   return 0;
 return 1;
}

/* AdvanceInd sets the next trial value combination for the independent
   variables.  It returns 1 when all such combinations have been
   tested. */
int AdvanceInd (void) {

  int carry=1, i, t;

 for (i=0; i<ict && carry;i++) {
  t = 1+P[I[i]].v;
  P[I[i]].v = t%2;
  carry = t/2;
 }
 return carry;
}

/* This updates the possible settings for a valid variable assignment.*/
void UpdateDepInt (void) {

  int i;

 for (i=0;i<ict;i++)
  if (P[I[i]].v != 0) P[I[i]].p = 1; /* Mine possible */
  else P[I[i]].n = 1; /* Mine absence possible */
 for (i=0;i<dct;i++)
  if (P[D[i].v].v != 0) P[D[i].v].p = 1; /* Mine possible */
  else P[D[i].v].n = 1; /* Mine absence possible */
}

/* Try all possible assignments of the independent variables and see
   if they set the dependent variables properly. */
void TrialandError (void) {

 do {
  EvaluateDep ();
  if (ValidDep ()) UpdateDepInt ();
 } while (!AdvanceInd ());
}

/* This evaluates the dependent variables from the independent
   variables. */
void EvaluateDep (void) {

  int i, j;

 for (i=0; i < dct; i++) {
  P[D[i].v].v = EQ[D[i].eqn][vars];
  for (j=D[i].v+1; j<vars;j++)
   P[D[i].v].v -= EQ[D[i].eqn][j]*P[j].v;
 }
}

/* This prints the information as specified. */
void PrintResult (void) {

  static int cs = 0;
  int first, i;

 fprintf (out,"Case %d:\n",++cs);
 fprintf (out,"    Cells with mines: ");
 first = 1;
 for (i=0;i<vars;i++)
  if (P[i].p && !P[i].n) {/* Mine possible but mine absence not poss */
   if (first) first = 0;
   else fprintf (out,", ");
   fprintf (out,"(%d,%d)",P[i].i+1,P[i].j+1);
  }
 fprintf (out,"\n    Cells without mines: ");
 first = 1;
 for (i=0;i<vars;i++)
  if (!P[i].p && P[i].n) {/* Mine absence possible but mine not poss */
   if (first) first = 0;
   else fprintf (out,", ");
   fprintf (out,"(%d,%d)",P[i].i+1,P[i].j+1);
  }
 fprintf (out,"\n\n");
}