1: // Homework 6.3: FIRE!
    2: 
    3: // Build a map of the distance from each point to the nearest door by
    4: // setting all distances to infinity, except the door squares which are
    5: // zero, and then repeatedly lowering each space to the minimum of its
    6: // neighbors plus the cost (time) of leaving the space.
    7: // (basically Dijkstra's algorithm...)
    8: 
    9: #include <iostream.h>
   10: 
   11: #define INF 10000
   12: 
   13: char map[50][50];
   14: int dist[50][50];
   15: 
   16: int main() {
   17:   int w, h, a, na;
   18:   cin >> w >> h >> a >> na;
   19:   char c;
   20:   int x, y;
   21:   for (x=0; x<w; x++) for (y=0; y<h; y++)
   22:     { map[x][y] = ' '; dist[x][y] = INF; }
   23:   for (x=0; x<w; x++) map[x][0] = map[x][h-1] = 'W';
   24:   for (y=0; y<h; y++) map[0][y] = map[w-1][y] = 'W';
   25:   while (cin >> c >> x >> y && (c == 'D' || c == 'T')) {
   26:     map[x][y] = c;
   27:     if (c == 'D') dist[x][y] = 0;
   28:   }
   29: 
   30:   int i, j, flag=1;
   31:   while (flag) {
   32:     flag = 0;
   33:     for (i=0; i<w; i++)
   34:       for (j=0; j<h; j++) {
   35:         if (map[i][j] != ' ') continue;
   36:           int m, n, minn = INF, aisle=1;
   37:           for (m=-1; m<=1; m++)
   38:             for (n=-1; n<=1; n++)
   39:               if (i+m >= 0 && i+m < w && j+n >= 0 && j+n < h && (m||n)) {
   40:                 if (map[i+m][j+n] == 'T') aisle=0;
   41:                 if (dist[i+m][j+n] < minn && (!m||!n)) minn = dist[i+m][j+n];
   42:               }
   43:         if (minn + (aisle ? a : na) < dist[i][j]) {
   44:           dist[i][j] = minn + (aisle ? a : na);
   45:           flag = 1;
   46:         }
   47:       }
   48:   }
   49: 
   50:   do {
   51:     cout << "The patron located at position (" << x << ", " << y <<
   52:       ") will require " << dist[x][y] << " seconds to exit the building." <<
   53:       endl;
   54:   } while (cin >> c >> x >> y && c == 'P');
   55:   cout << "END OF OUTPUT" << endl;
   56:   return 0;
   57: }