POJ: Evacuation

`35 5XXDXXX...XD...XX...DXXXXX5 12XXXXXXXXXXXXX..........DX.XXXXXXXXXXX..........XXXXXXXXXXXXX5 5XDXXXX.X.DXX.XXD.X.XXXXDX`
`321impossible`
`#include <cstdio>#include <vector>#include <queue>using namespace std;#define ROW 13#define COL 13#define MAXITEMS ((ROW) * (COL))int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};int distance2door[ROW][COL][ROW][COL];vector<pair<int, int> > doors;vector<pair<int, int> > persons;char fields[ROW][COL];vector<int> G[MAXITEMS * MAXITEMS];int match[MAXITEMS * MAXITEMS];bool used[MAXITEMS * MAXITEMS];int V;void add_adge(int u, int v) {  G[u].push_back(v);  G[v].push_back(u);}bool dfs(int v) {  used[v] = true;  for (int i = 0; i < G[v].size(); ++i) {    int u = G[v][i];    int w = match[u];    if (w < 0 || !used[w] && dfs(w)) {      match[v] = u;      match[u] = v;      return true;    }  }  return false;}void computeDistance(int x, int y, int d[ROW][COL]) {  queue<pair<int, int> > q;  d[x][y] = 0;  q.push(make_pair(x, y));while (!q.empty()) {    int i = q.front().first;    int j = q.front().second;    q.pop();for (int k = 0; k < 4; ++k) {      int px = i + dx[k];      int py = j + dy[k];      if (px >= 0 && px < ROW && py >= 0 && py < COL && d[px][py] == -1 && fields[px][py] == '.') {        d[px][py] = d[i][j] + 1;        q.push(make_pair(px, py));      }    }  }}int main(int argc, char *argv[]) {  int times;  scanf("%d", &times);  while (times--) {    int rows, cols;    doors.clear();    persons.clear();    memset(distance2door, -1, sizeof(distance2door));    getchar();    scanf("%d%d", &rows, &cols);    for (int i = 0; i < rows; ++i) {      getchar();      for (int j = 0; j < cols; ++j) {        char c;        scanf("%c", &fields[i][j]);        if (fields[i][j] == 'D') {          doors.push_back(make_pair(i,j));        } else if (fields[i][j] == '.') {          persons.push_back(make_pair(i,j));        }      }    }for (int i = 0; i < doors.size(); ++i)      computeDistance(doors[i].first, doors[i].second, distance2door[doors[i].first][doors[i].second]);int d = doors.size();    int p = persons.size();    for (int v = 0; v < rows * cols * doors.size(); ++v) G[v].clear();    for (int i = 0; i < d; ++i) {      for (int j = 0; j < p; ++j) {        if (distance2door[doors[i].first][doors[i].second][persons[j].first][persons[j].second] >= 0) {          for (int k = distance2door[doors[i].first][doors[i].second][persons[j].first][persons[j].second]; k <= rows * cols; ++k)            add_adge((k-1) * d + i, rows * cols * d + j);        }      }    }    if (persons.size() == 0) {      printf("0\n");    } else {      int num = 0;      memset(match, -1, sizeof(match));      for (int v = 0; v < rows * cols * doors.size(); ++v) {        memset(used, 0, sizeof(used));        if (dfs(v)) {          if (++num == persons.size()) {            printf("%d\n", v / (int)doors.size() + 1);            break;          }        }      }      if (num != persons.size()) printf("impossible\n");    }  }  return 0;}`

--

--