1: // Example 6.4: The Unsinkable Ship?
    2: 
    3: // Store in the shipmap the time that each square will flood.
    4: // Then do a DFS, backtracking whenever you hit a square that has already
    5: // flooded or whenever you run out of lifeboats.
    6: // Keep track of squares on the successful path by turning them into
    7: // PATH+(step number).
    8: 
    9: #include <iostream.h>
   10: #include <stdio.h>
   11: #include <string.h>
   12: 
   13: #define FLOOD 1000
   14: #define NEVER 999
   15: #define PATH  2000
   16: 
   17: int shipmap[20][20];
   18: int w, h;
   19: int A;  /* flood rate */
   20: int move;
   21: int nboats;
   22: 
   23: int escape(int x, int y) {
   24:   if (nboats <= move/2) return 0;
   25:   if (move >= A*(shipmap[y][x]-FLOOD)) return 0;
   26:   if (x == 0 && y == 0) { shipmap[y][x] = PATH+move; return 1; }
   27:   if (move >= A*(shipmap[y][x]-FLOOD)-1) return 0;
   28:   int t = shipmap[y][x];
   29:   shipmap[y][x] = '.';  /* keep us from crossing this square again */
   30:   move++;
   31:   if (x > 0 && escape(x-1, y)) { shipmap[y][x] = PATH+ --move; return 1; }
   32:   if (y > 0 && escape(x, y-1)) { shipmap[y][x] = PATH+ --move; return 1; }
   33:   if (x < w-1 && escape(x+1, y)) { shipmap[y][x] = PATH+ --move; return 1; }
   34:   if (y < h-1 && escape(x, y+1)) { shipmap[y][x] = PATH+ --move; return 1; }
   35:   move--;
   36:   shipmap[y][x] = t;
   37:   return 0;
   38: }
   39: 
   40: int main() {
   41:   int nships, c, i, j, yx, yy;
   42:   cin >> nships;
   43:   for (c=0; c<nships; c++) {
   44:     printf("Sinking Ship #%d\n", c+1);
   45: 
   46:     /* read in ship data */
   47:     cin >> nboats >> A >> h;
   48:     move = 0;
   49:     for (j=0; j<h; j++) {
   50:       char buf[21];
   51:       cin >> buf;
   52:       w = strlen(buf);
   53:       for (int k=0; k<w; k++) {
   54:         shipmap[j][k] = buf[k];
   55:         if (shipmap[j][k] == 'Y') {
   56:           shipmap[j][k] = 'O';
   57:           yx = k;  yy = j;
   58:         }
   59:       }
   60:     }
   61: 
   62:     /* set each square to the time at which it will flood */
   63:     for (i=0; i<h; i++)
   64:       for (j=0; j<w; j++)
   65:         shipmap[i][j] = (shipmap[i][j] == 'F') ? (FLOOD + 0) : (FLOOD+NEVER);
   66:     int flag;
   67:     do {
   68:       flag = 0;
   69:       for (i=0; i<h; i++)
   70:         for (j=0; j<w; j++) {
   71:           if (shipmap[i][j] != FLOOD+NEVER) continue;
   72:           int neighborflood = FLOOD+NEVER;
   73:           if (i > 0 && shipmap[i-1][j] < neighborflood)
   74:             neighborflood = shipmap[i-1][j];
   75:           if (j > 0 && shipmap[i][j-1] < neighborflood)
   76:             neighborflood = shipmap[i][j-1];
   77:           if (i < h-1 && shipmap[i+1][j] < neighborflood)
   78:             neighborflood = shipmap[i+1][j];
   79:           if (j < w-1 && shipmap[i][j+1] < neighborflood)
   80:             neighborflood = shipmap[i][j+1];
   81:           if (neighborflood != FLOOD+NEVER) {
   82:             shipmap[i][j] = neighborflood + 1;
   83:             flag = 1;
   84:           }
   85:         }
   86:     } while (flag);
   87: 
   88:     /* try to escape, and print out the map (if any) */
   89:     if (escape(yx, yy)) {
   90:       for (int y=0; y<h; y++) {
   91:         for (int x=0; x<w; x++)
   92:           if (shipmap[y][x] >= PATH) printf("%3d", shipmap[y][x]-PATH);
   93:             else printf("  X");
   94:         putchar('\n');
   95:       }
   96:     }
   97:     else
   98:       printf("No Path Exists.\n");
   99: 
  100:     putchar('\n');
  101:   }
  102:   printf("All Sets Run.\n");
  103:   return 0;
  104: }