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: }