Submission #307215


Source Code Expand

#include <bits/stdc++.h>
using namespace std;

const int INF = 1<<28;

struct Edge {
  int to, cost, cap, rev, rflag;
  Edge(int to, int cost, int cap, int rev, int rflag)
    : to(to), cost(cost), cap(cap), rev(rev), rflag(rflag) {}
  Edge() {}
};

typedef vector<vector<Edge> > Graph;

const int MAXH = 55;
const int MAXW = 55;
const int di[] = {0,1,0,-1};
const int dj[] = {1,0,-1,0};
int H, W;
char G[MAXH][MAXW];

void addEdgeF(int from, int to, int cost, int cap, Graph &g) {
  g[from].push_back(Edge(to,cost,cap,g[to].size(),0));
  g[to].push_back(Edge(from,-cost,0,(int)g[from].size()-1,1));
}

int dfsF(int v, int t, int f, bool *used, Graph &g) {
  if(v == t) return f;
  used[v] = true;
  for(int i = 0; i < g[v].size(); ++i) {
    Edge &e = g[v][i];
    if(!used[e.to] && e.cap > 0) {
      int d = dfsF(e.to, t, min(f, e.cap), used, g);
      if(d > 0) {
        e.cap -= d;
        g[e.to][e.rev].cap += d;
        return d;
      }
    }
  }
  return 0;
}

int maxFlow(int s, int t, Graph g) {
  int flow = 0;
  bool *used = new bool[g.size()];
  while(1) {
    fill(used, used + g.size(), false);
    int f = dfsF(s, t, INF, used, g);
    if(f == 0) break;
    flow += f;
  }
  delete [] used;
  return flow;
}

typedef pair<int,int> Pair;

// O(FV^2)
int minCostFlow(int s, int t, int f, Graph &g) {
  int V = g.size();
  vector<int> h(V), dist(V), prevv(V), preve(V);
  int res = 0;
  fill(h.begin(), h.end(), 0);
  while(f > 0) {
    priority_queue<Pair, vector<Pair>, greater<Pair> > que;
    fill(dist.begin(), dist.end(), INF);
    dist[s] = 0;
    que.push(Pair(0, s));
    while(!que.empty()) {
      Pair p = que.top(); que.pop();
      int v = p.second;
      if(dist[v] < p.first) continue;
      for(int i = 0; i < g[v].size(); ++i) {
        Edge &e = g[v][i];
        int tmp = dist[v] + e.cost + h[v] - h[e.to];
        if(e.cap > 0 && dist[e.to] > tmp) {
          dist[e.to] = tmp;
          prevv[e.to] = v;
          preve[e.to] = i;
          que.push(Pair(dist[e.to], e.to));
        }
      }
    }
    if(dist[t] == INF) {
      return -1;
    }
    for(int v = 0; v < V; ++v) h[v] += dist[v];

    int d = f;
    for(int v = t; v != s; v = prevv[v]) {
      d = min(d, g[prevv[v]][preve[v]].cap);
    }
    f -= d;
    res += d * h[t];
    for(int v = t; v != s; v = prevv[v]) {
      Edge &e = g[prevv[v]][preve[v]];
      e.cap -= d;
      g[v][e.rev].cap += d;
    }
  }
  return res;
}

int bfs(int si, int sj, int gi, int gj) {
  vector<vector<int> > cost(H, vector<int>(W, INF));
  queue<pair<int,int> > que;
  que.push(make_pair(si, sj));
  cost[si][sj] = 0;
  while(que.size()) {
    int pi = que.front().first;
    int pj = que.front().second;
    que.pop();
    for(int k = 0; k < 4; ++k) {
      int ni = pi + di[k];
      int nj = pj + dj[k];
      if(ni < 0 || ni >= H) continue;
      if(nj < 0 || nj >= W) continue;
      if(G[ni][nj] == '#')continue;
      if(cost[ni][nj] != INF) continue;
      que.push(make_pair(ni, nj));
      cost[ni][nj] = cost[pi][pj] + 1;
      if(ni == gi && nj == gj) return cost[ni][nj];
    }
  }
  return INF;
}

void dfs(int v, char c, Graph &g) {
  if(v < H*W) {
    int i = v/W, j = v%W;
    if(G[i][j] == '.') G[i][j] = c;
  }
  for(int i = 0; i < g[v].size(); ++i) {
    const Edge &e = g[v][i];
    if(e.rflag && e.cap) {
      dfs(e.to, c, g);
      break;
    }
  }
}

int main() {
  cin >> H >> W;
  int ai, aj, bi, bj, si, sj;
  for(int i = 0; i < H; ++i) {
    for(int j = 0; j < W; ++j) {
      cin >> G[i][j];
      if(G[i][j] == 'A') {
        ai = i; aj = j;
      }
      if(G[i][j] == 'B') {
        bi = i; bj = j;
      }
      if(G[i][j] == 'S') {
        si = i; sj = j;
      }
    }
  }
  int costA = bfs(si, sj, ai, aj);
  int costB = bfs(si, sj, bi, bj);

  //void addEdgeF(int from, int to, int cost, int cap, Graph &g) {
  Graph g(H*W*2+1);
  int src = H*W+si*W+sj;
  int dst = H*W*2;
  for(int i = 0; i < H*W; ++i) {
    if(G[i/W][i%W] != '#')
      addEdgeF(i, H*W+i, 0, 1, g);
  }
  addEdgeF(H*W + ai*W+aj, dst, 0, 1, g);
  addEdgeF(H*W + bi*W+bj, dst, 0, 1, g);
  for(int i = 0; i < H; ++i) {
    for(int j = 0; j < W; ++j) {
      int from = H*W+i * W + j;
      for(int k = 0; k < 4; ++k) {
        int ni = i + di[k];
        int nj = j + dj[k];
        if(ni < 0 || ni >= H) continue;
        if(nj < 0 || nj >= W) continue;
        int to = ni * W + nj;
        addEdgeF(from, to, 1, 1, g);
      }
    }
  }
  int sum = minCostFlow(src, dst, 2, g);
  if(sum != costA + costB) {
    cout << "NA" << endl;
  } else {
    dfs(ai*W+aj, 'a', g);
    dfs(bi*W+bj, 'b', g);
    for(int i = 0; i < H; ++i) {
      for(int j = 0; j < W; ++j) {
        cout << G[i][j];
      }
      cout << endl;
    }
  }
  return 0;
}

Submission Info

Submission Time
Task D - Maze
User zukky
Language C++ (G++ 4.6.4)
Score 100
Code Size 4936 Byte
Status AC
Exec Time 32 ms
Memory 1948 KB

Judge Result

Set Name all
Score / Max Score 100 / 100
Status
AC × 41
Set Name Test Cases
all manual_j1.txt, manual_j10.txt, manual_j11.txt, manual_j12.txt, manual_j13.txt, manual_j14.txt, manual_j15.txt, manual_j2.txt, manual_j3.txt, manual_j4.txt, manual_j5.txt, manual_j6.txt, manual_j7.txt, manual_j8.txt, manual_j9.txt, manual_k1.txt, manual_k2.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_max_01.txt, random_max_02.txt, random_max_03.txt, random_max_04.txt, random_max_05.txt, random_max_06.txt, random_max_07.txt, random_max_08.txt, random_max_09.txt, random_max_10.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, white_01.txt, white_02.txt, white_03.txt, white_04.txt
Case Name Status Exec Time Memory
manual_j1.txt AC 24 ms 924 KB
manual_j10.txt AC 22 ms 928 KB
manual_j11.txt AC 32 ms 1824 KB
manual_j12.txt AC 24 ms 928 KB
manual_j13.txt AC 24 ms 816 KB
manual_j14.txt AC 24 ms 928 KB
manual_j15.txt AC 23 ms 924 KB
manual_j2.txt AC 29 ms 1636 KB
manual_j3.txt AC 24 ms 932 KB
manual_j4.txt AC 24 ms 928 KB
manual_j5.txt AC 22 ms 928 KB
manual_j6.txt AC 22 ms 804 KB
manual_j7.txt AC 23 ms 672 KB
manual_j8.txt AC 22 ms 800 KB
manual_j9.txt AC 22 ms 928 KB
manual_k1.txt AC 29 ms 1948 KB
manual_k2.txt AC 30 ms 1864 KB
random_01.txt AC 27 ms 1700 KB
random_02.txt AC 31 ms 1816 KB
random_03.txt AC 29 ms 1684 KB
random_04.txt AC 29 ms 1808 KB
random_05.txt AC 29 ms 1304 KB
random_06.txt AC 26 ms 1428 KB
random_max_01.txt AC 29 ms 1824 KB
random_max_02.txt AC 28 ms 1820 KB
random_max_03.txt AC 32 ms 1708 KB
random_max_04.txt AC 32 ms 1740 KB
random_max_05.txt AC 30 ms 1816 KB
random_max_06.txt AC 29 ms 1692 KB
random_max_07.txt AC 30 ms 1696 KB
random_max_08.txt AC 31 ms 1752 KB
random_max_09.txt AC 31 ms 1696 KB
random_max_10.txt AC 30 ms 1692 KB
sample_01.txt AC 24 ms 804 KB
sample_02.txt AC 24 ms 800 KB
sample_03.txt AC 25 ms 792 KB
sample_04.txt AC 25 ms 924 KB
white_01.txt AC 32 ms 1828 KB
white_02.txt AC 32 ms 1820 KB
white_03.txt AC 30 ms 1832 KB
white_04.txt AC 29 ms 1820 KB