1 /* hex.java MCPC 2008 Problem C by Andy Harrington
  2 allow only 1 or 2 digit numbers, max 2 *'s so int calculations work
  3 */
  4 
  5 import java.util.*;
  6 import java.io.*;
  7 
  8 public class hex
  9 {
 10     static char[][] hex; // input pattern
 11     static char[] seq;  // current proposed soluton sequence
 12     static int nMax;    // total number of tiles
 13     // offsets to neighbors:
 14     static int[][] dc = { {1,  0, -1, -1, -1, 0},   // in even row
 15                           {1,  1,  0, -1,  0, 1} }; // in odd row
 16     static int[] dr =     {0, -1, -1,  0,  1, 1};   // in each row
 17     static char DONE = '\0';  // initial array value
 18     static int nSol;  //judge data
 19 
 20     public static void main(String[] args) throws Exception {
 21         String file = (args.length > 0) ? args[0] : "hex.in";
 22         Scanner in = new Scanner(new File(file));
 23         int r  = in.nextInt();
 24         while (r  > 0) {
 25             int c = in.nextInt();
 26             hex = new char[r+2][c+3]; // leave border; no boundary checks
 27             for (int i = 1; i <= r; i++) 
 28                 for (int j = 1; j <= c + 1 - i % 2; j++)
 29                     hex[i][j] = in.next().charAt(0);
 30             nMax = r*c + r/2;
 31             seq = new char[nMax+1];  // convenient to append final '='
 32             seq[nMax] = '=';         //   to trigger second evaluation
 33             nSol = 0; // judge check
 34             for (int i = 1; i <= r; i++)
 35                 for (int j = 1; j <= c + 1 - i % 2; j++) 
 36                     if (Character.isDigit(hex[i][j])) 
 37                         solve(i, j, 0, 0);
 38             if (nSol == 0) // judge check
 39                 System.out.println("#### NO SOLUTION!");
 40             r = in.nextInt();
 41         }
 42     }
 43 
 44     // use hex[r][c] next if not DONE and number of digits legal.
 45     //   nDigits before; n is current length of seq without hex[r][c]
 46     static void solve(int r, int c, int n, int nDigits) {
 47         char lastCh = hex[r][c];
 48         nDigits = Character.isDigit(lastCh) ? nDigits+1 : 0;
 49         if (lastCh == DONE || nDigits > 2 ||   // 2 is max number of digits
 50                               nDigits == 2 && seq[n-1] == '0') // leading '0'
 51             return;
 52         seq[n] = lastCh;
 53         if (n < nMax - 1) { // add another character
 54             hex[r][c] = DONE;  // don't let path come back here
 55             for (int i = 0; i < 6; i++) //
 56                  solve(r + dr[i], c + dc[r%2][i], n+1, nDigits);
 57             hex[r][c] = lastCh; // revert to previous state for backtracking
 58         }
 59         else if (nDigits > 0) // full seq; end must be digit
 60             checkEqual();  
 61      }
 62 
 63     static void checkEqual() { // have seq[0..nMax], seq[nMax] set to '='
 64         // assume seq: digit(s), op, digit(s), op, ... digit(s), second '='
 65         int leftExpr = 0;  // set after first '='
 66         int expr = 0;  // currently accumulating expression
 67         char lastOp = '+';  // adding to 0 is innocuous initialization
 68         int digits = 0;  // value of current digit sequence
 69         for (int i = 0; i <= nMax; i++) {
 70             char ch = seq[i];
 71             if (Character.isDigit(ch)) 
 72                 digits = 10*digits + ch - '0';
 73             else {
 74                 switch(lastOp) {  // evaluate so far
 75                     case '+': expr += digits; break;
 76                     case '-': expr -= digits; break;
 77                     case '*': expr *= digits; break;
 78                     case '/':  { // no division by 0, exact integer result
 79                         if (digits == 0 || expr % digits != 0)
 80                             return;
 81                         expr /= digits; break;
 82                     }
 83                 }
 84                 digits = 0;
 85                 if (ch != '=')  // continue expression
 86                     lastOp = ch;
 87                 else if (i < nMax) { // first =
 88                     leftExpr = expr;
 89                     lastOp = '+'; // start expr calc over
 90                     expr = 0;
 91                 }
 92                 else if (leftExpr == expr) { // second equal at end, and match
 93                     nSol++; // judge check for 3 lines
 94                     if (nSol > 1)
 95                         System.out.print("!!!  ");           
 96                     for (int j = 0; j < nMax; j++)
 97                         System.out.print(seq[j]);
 98                     System.out.println();
 99                 }
100             }
101         }
102     }
103 }