java 解法, 执行用时: 1163 ms, 内存消耗: 67.4 MB, 提交时间: 2023-10-27 22:28:52
class Solution {
int INF=100000;
int dir[][]=new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
public int guardCastle(String[] grid) {
char A[][]=to(grid);
int N=A.length*A[0].length;
List<Edge>[] graph = MaxFlowDinic.createGraph(4*N+10);
int source=N*4+1;
int dest=N*4+2;
int special=N*4+3;
for(int i=0;i<A.length;i++){
for(int j=0;j<A[0].length;j++){
if(A[i][j]=='#')continue;
int id1=i*A[0].length+j;
int id2=id1+N;
//connect itself
if(A[i][j]=='.'){
MaxFlowDinic.addEdge(graph,id1,id2,1);
}
else{
MaxFlowDinic.addEdge(graph,id1,id2,INF);
}
if(A[i][j]=='S'){
MaxFlowDinic.addEdge(graph,id2,dest,INF);
}
else if(A[i][j]=='C'){
MaxFlowDinic.addEdge(graph,source,id1,INF);
}
else if(A[i][j]=='P'){
MaxFlowDinic.addEdge(graph,id2,special,INF);
MaxFlowDinic.addEdge(graph,special,id1,INF);
}
for(int p[]:dir){
int x=i+p[0];
int y=j+p[1];
if(x<0||x>=A.length||y<0||y>=A[0].length)continue;
int id3=x*A[0].length+y;
MaxFlowDinic.addEdge(graph,id2,id3,INF);
}
}
}
//run maxFlow
int flow = MaxFlowDinic.maxFlow(graph,source,dest);
if(flow>N)return -1;
return flow;
}
public char[][] to(String grid[]){
char A[][]=new char[grid.length][grid[0].length()];
for(int i=0;i<grid.length;i++){
for(int j=0;j<grid[0].length();j++){
A[i][j]=grid[i].charAt(j);
}
}
return A;
}
}
class Edge {
int t, rev, cap, f;
public Edge(int t, int rev, int cap) {
this.t = t;
this.rev = rev;
this.cap = cap;
}
}
class MaxFlowDinic {
public static List<Edge>[] createGraph(int nodes) {
List<Edge>[] graph = new List[nodes];
for (int i = 0; i < nodes; i++)
graph[i] = new ArrayList<>();
return graph;
}
public static void addEdge(List<Edge>[] graph, int s, int t, int cap) {
graph[s].add(new Edge(t, graph[t].size(), cap));
graph[t].add(new Edge(s, graph[s].size() - 1, 0));
}
static boolean dinicBfs(List<Edge>[] graph, int src, int dest, int[] dist) {
Arrays.fill(dist, -1);
dist[src] = 0;
int[] Q = new int[graph.length];
int sizeQ = 0;
Q[sizeQ++] = src;
for (int i = 0; i < sizeQ; i++) {
int u = Q[i];
for (Edge e : graph[u]) {
if (dist[e.t] < 0 && e.f < e.cap) {
dist[e.t] = dist[u] + 1;
Q[sizeQ++] = e.t;
}
}
}
return dist[dest] >= 0;
}
static int dinicDfs(List<Edge>[] graph, int[] ptr, int[] dist, int dest, int u, int f) {
if (u == dest)
return f;
for (; ptr[u] < graph[u].size(); ++ptr[u]) {
Edge e = graph[u].get(ptr[u]);
if (dist[e.t] == dist[u] + 1 && e.f < e.cap) {
int df = dinicDfs(graph, ptr, dist, dest, e.t, Math.min(f, e.cap - e.f));
if (df > 0) {
e.f += df;
graph[e.t].get(e.rev).f -= df;
return df;
}
}
}
return 0;
}
public static int maxFlow(List<Edge>[] graph, int src, int dest) {
int flow = 0;
int[] dist = new int[graph.length];
while (dinicBfs(graph, src, dest, dist)) {
int[] ptr = new int[graph.length];
while (true) {
int df = dinicDfs(graph, ptr, dist, dest, src, Integer.MAX_VALUE);
if (df == 0)
break;
flow += df;
}
}
return flow;
}
/*public static void main(String[] args) {
List<Edge>[] graph = createGraph(3);
addEdge(graph, 0, 1, 3);
addEdge(graph, 0, 2, 2);
addEdge(graph, 1, 2, 2);
System.out.println(4 == maxFlow(graph, 0, 2));
}*/
}
python3 解法, 执行用时: 692 ms, 内存消耗: 16.5 MB, 提交时间: 2023-10-27 22:28:23
class Solution:
def guardCastle(self, grid: List[str]) -> int:
# 0 = S, 1 = C, 2 = P
INF = 1000000000
N = len(grid)
M = len(grid[0])
ans = INF
for P in ('C', 'S'):
last_endpoint = None
# 00, 01, 10, 11
dp = [0, 0, 0, 0]
for j in range(M):
current = grid[0][j], grid[1][j]
current = tuple(P if c == 'P' else c for c in current)
if 'S' in current:
if 'C' in current:
dp[3] = INF
break
endpoint = 0
target = 'S'
elif 'C' in current:
endpoint = 1
target = 'C'
else:
endpoint = None
target = None
if current == (target, target):
if last_endpoint == 1 - endpoint:
dp = [INF, INF, INF, dp[0]]
else:
dp = [INF, INF, INF, dp[3]]
elif current == (target, '#'):
if last_endpoint == 1 - endpoint:
dp = [INF, INF, dp[1], dp[1]]
else:
dp = [INF, INF, dp[3], dp[3]]
elif current == ('#', target):
if last_endpoint == 1 - endpoint:
dp = [INF, dp[2], INF, dp[2]]
else:
dp = [INF, dp[3], INF, dp[3]]
elif current == (target, '.'):
if last_endpoint == 1 - endpoint:
dp = [INF, INF, dp[1] + 1, dp[0]]
dp[3] = min(dp[2], dp[3])
else:
dp = [INF, INF, dp[3] + 1, dp[3]]
elif current == ('.', target):
if last_endpoint == 1 - endpoint:
dp = [INF, dp[2] + 1, INF, dp[0]]
dp[3] = min(dp[1], dp[3])
else:
dp = [INF, dp[3] + 1, INF, dp[3]]
elif current == ('.', '.'):
dp[0] = min(dp[0], dp[1] + 1, dp[2] + 1, dp[3] + 2)
dp[1] = dp[2] = min(dp[0], dp[3] + 1)
elif current == ('.', '#'):
dp[0] = dp[1] = min(dp[1], dp[3] + 1)
dp[2] = dp[3]
elif current == ('#', '.'):
dp[0] = dp[2] = min(dp[2], dp[3] + 1)
dp[1] = dp[3]
else:
dp[0] = dp[1] = dp[2] = dp[3]
if endpoint is not None:
last_endpoint = endpoint
ans = min(ans, dp[3])
if ans >= INF:
return -1
else:
return ans
cpp 解法, 执行用时: 352 ms, 内存消耗: 13.4 MB, 提交时间: 2023-10-27 22:27:51
int f[10010][4][4];
class Solution {
private:
static constexpr int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public:
int check(const vector<string>& grid) {
int n = grid[0].size();
// check if no (castle, demon) neighbor pair exists
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < n; ++j) {
for (int d = 0; d < 4; ++d) {
int ni = i + dirs[d][0];
int nj = j + dirs[d][1];
if (ni >= 0 && ni < 2 && nj >= 0 && nj < n) {
if (grid[i][j] == 'C' && grid[ni][nj] == 'S') {
return INT_MAX;
}
if (grid[i][j] == 'S' && grid[ni][nj] == 'C') {
return INT_MAX;
}
}
}
}
}
// f[i][s1][s2] = ith column, s1, s2, minimum barriers to put
// s1, s2 = (0=empty, 1=castle, 2=demon, 3=stone)
memset(f, 0x3f, sizeof(f));
f[0][0][0] = 0;
unordered_map<char, int> rep = {{'.', 0}, {'C', 1}, {'S', 2}, {'#', 3}};
auto update = [&](int i, int s1, int s2, int t1, int t2, int extra) {
if (s1 == 1 || s1 == 2) {
if (s1 + t1 == 3) {
return;
}
if (t1 == 0) {
t1 = s1;
}
}
if (s2 == 1 || s2 == 2) {
if (s2 + t2 == 3) {
return;
}
if (t2 == 0) {
t2 = s2;
}
}
if ((t1 == 1 || t1 == 2) && (t1 + t2 == 3)) {
return;
}
if ((t1 == 1 || t1 == 2) && t2 == 0) {
t2 = t1;
}
if ((t2 == 1 || t2 == 2) && t1 == 0) {
t1 = t2;
}
f[i][t1][t2] = min(f[i][t1][t2], f[i - 1][s1][s2] + extra);
};
for (int i = 1; i <= n; ++i) {
int t1 = rep[grid[0][i - 1]];
int t2 = rep[grid[1][i - 1]];
for (int s1 = 0; s1 < 4; ++s1) {
for (int s2 = 0; s2 < 4; ++s2) {
update(i, s1, s2, t1, t2, 0);
if (grid[0][i - 1] == '.') {
update(i, s1, s2, 3, t2, 1);
}
if (grid[1][i - 1] == '.') {
update(i, s1, s2, t1, 3, 1);
}
if (grid[0][i - 1] == '.' && grid[1][i - 1] == '.') {
update(i, s1, s2, 3, 3, 2);
}
}
}
}
int ans = INT_MAX;
for (int i = 0; i < 4; ++i) {
for (int j = 0; j < 4; ++j) {
ans = min(ans, f[n][i][j]);
}
}
return ans;
}
int guardCastle(vector<string>& grid) {
int n = grid[0].size();
int ans = INT_MAX;
// mark every portal as castle
auto g1 = grid;
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < n; ++j) {
if (g1[i][j] == 'P') {
g1[i][j] = 'C';
}
}
}
ans = min(ans, check(g1));
// mark every portal as demon
auto g2 = grid;
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < n; ++j) {
if (g2[i][j] == 'P') {
g2[i][j] = 'S';
}
}
}
ans = min(ans, check(g2));
if (ans == INT_MAX) {
ans = -1;
}
return ans;
}
};
cpp 解法, 执行用时: 1748 ms, 内存消耗: 367.3 MB, 提交时间: 2023-10-27 22:27:23
namespace atcoder {
namespace internal {
template <class T> struct simple_queue {
std::vector<T> payload;
int pos = 0;
void reserve(int n) { payload.reserve(n); }
int size() const { return int(payload.size()) - pos; }
bool empty() const { return pos == int(payload.size()); }
void push(const T& t) { payload.push_back(t); }
T& front() { return payload[pos]; }
void clear() {
payload.clear();
pos = 0;
}
void pop() { pos++; }
};
} // namespace internal
} // namespace atcoder
namespace atcoder {
template <class Cap> struct mf_graph {
public:
mf_graph() : _n(0) {}
explicit mf_graph(int n) : _n(n), g(n) {}
int add_edge(int from, int to, Cap cap) {
// printf("edge = %d %d %d\n", from, to, cap);
assert(0 <= from && from < _n);
assert(0 <= to && to < _n);
assert(0 <= cap);
int m = int(pos.size());
pos.push_back({from, int(g[from].size())});
int from_id = int(g[from].size());
int to_id = int(g[to].size());
if (from == to) to_id++;
g[from].push_back(_edge{to, to_id, cap});
g[to].push_back(_edge{from, from_id, 0});
return m;
}
struct edge {
int from, to;
Cap cap, flow;
};
edge get_edge(int i) {
int m = int(pos.size());
assert(0 <= i && i < m);
auto _e = g[pos[i].first][pos[i].second];
auto _re = g[_e.to][_e.rev];
return edge{pos[i].first, _e.to, _e.cap + _re.cap, _re.cap};
}
std::vector<edge> edges() {
int m = int(pos.size());
std::vector<edge> result;
for (int i = 0; i < m; i++) {
result.push_back(get_edge(i));
}
return result;
}
void change_edge(int i, Cap new_cap, Cap new_flow) {
int m = int(pos.size());
assert(0 <= i && i < m);
assert(0 <= new_flow && new_flow <= new_cap);
auto& _e = g[pos[i].first][pos[i].second];
auto& _re = g[_e.to][_e.rev];
_e.cap = new_cap - new_flow;
_re.cap = new_flow;
}
Cap flow(int s, int t) {
return flow(s, t, std::numeric_limits<Cap>::max());
}
Cap flow(int s, int t, Cap flow_limit) {
assert(0 <= s && s < _n);
assert(0 <= t && t < _n);
assert(s != t);
std::vector<int> level(_n), iter(_n);
internal::simple_queue<int> que;
auto bfs = [&]() {
std::fill(level.begin(), level.end(), -1);
level[s] = 0;
que.clear();
que.push(s);
while (!que.empty()) {
int v = que.front();
que.pop();
for (auto e : g[v]) {
if (e.cap == 0 || level[e.to] >= 0) continue;
level[e.to] = level[v] + 1;
if (e.to == t) return;
que.push(e.to);
}
}
};
auto dfs = [&](auto self, int v, Cap up) {
if (v == s) return up;
Cap res = 0;
int level_v = level[v];
for (int& i = iter[v]; i < int(g[v].size()); i++) {
_edge& e = g[v][i];
if (level_v <= level[e.to] || g[e.to][e.rev].cap == 0) continue;
Cap d =
self(self, e.to, std::min(up - res, g[e.to][e.rev].cap));
if (d <= 0) continue;
g[v][i].cap += d;
g[e.to][e.rev].cap -= d;
res += d;
if (res == up) return res;
}
level[v] = _n;
return res;
};
Cap flow = 0;
while (flow < flow_limit) {
bfs();
if (level[t] == -1) break;
std::fill(iter.begin(), iter.end(), 0);
Cap f = dfs(dfs, t, flow_limit - flow);
if (!f) break;
flow += f;
}
return flow;
}
std::vector<bool> min_cut(int s) {
std::vector<bool> visited(_n);
internal::simple_queue<int> que;
que.push(s);
while (!que.empty()) {
int p = que.front();
que.pop();
visited[p] = true;
for (auto e : g[p]) {
if (e.cap && !visited[e.to]) {
visited[e.to] = true;
que.push(e.to);
}
}
}
return visited;
}
private:
int _n;
struct _edge {
int to, rev;
Cap cap;
};
std::vector<std::pair<int, int>> pos;
std::vector<std::vector<_edge>> g;
};
} // namespace atcoder
class Solution {
private:
static constexpr int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
static constexpr int INF = 20010;
public:
int guardCastle(vector<string>& grid) {
int n = grid[0].size();
// extra point for collecting portals & demons
// portal=n*4, demons=n*4+1
atcoder::mf_graph<int> g(n * 4 + 2);
int sx = -1, sy = -1;
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < n; ++j) {
int base_id = i * n + j;
if(grid[i][j]=='#') continue;
if (grid[i][j] == '.') {
g.add_edge(base_id * 2, base_id * 2 + 1, 1);
}
else if (grid[i][j] == 'C') {
g.add_edge(base_id * 2, base_id * 2 + 1, INF);
sx = i;
sy = j;
}
else if (grid[i][j] == 'S' || grid[i][j] == 'P') {
g.add_edge(base_id * 2, base_id * 2 + 1, INF);
}
if (grid[i][j] == 'S') {
g.add_edge(base_id * 2 + 1, n * 4 + 1, INF);
}
if (grid[i][j] == 'P') {
g.add_edge(base_id * 2 + 1, n * 4, INF);
g.add_edge(n * 4, base_id * 2, INF);
}
for (int d = 0; d < 4; ++d) {
int ii = i + dirs[d][0];
int jj = j + dirs[d][1];
if (ii >= 0 && ii < 2 && jj >= 0 && jj < n) {
if (grid[ii][jj] == '#') {
continue;
}
int case_id = ii * n + jj;
g.add_edge(base_id * 2 + 1, case_id * 2, INF);
}
}
}
}
int ans = g.flow((sx * n + sy) * 2, n * 4 + 1);
if (ans == INF) {
ans = -1;
}
return ans;
}
};
golang 解法, 执行用时: 8 ms, 内存消耗: 5.8 MB, 提交时间: 2023-10-27 22:26:49
func min(a, b int) int {
if a <= b {
return a
}
return b
}
func guardCastle(grid []string) int {
l := len(grid[0]) + 2
g0, g1, g0t, g1t := make([]byte, l), make([]byte, l), make([]byte, l), make([]byte, l)
copy(g0[1:], grid[0])
copy(g1[1:], grid[1])
g0[0], g0[l-1], g1[0], g1[l-1] = '.', '.', '.', '.'
copy(g0t, g0)
copy(g1t, g1)
cal1 := func(i, p int) int {
for j := p + 1; j <= i; j++ {
if (g0[j] == '#' && (g1[j] == '#' || g1[j-1] == '#')) ||
(g1[j] == '#' && (g0[j] == '#' || g0[j-1] == '#')) {
return 0
}
}
for j := i; j >= p; j-- {
if g0[j] == '#' {
if j < i && g1[j+1] == '.' {
g1[j+1] = '#'
}
return 1
}
if g1[j] == '#' {
if j < i && g0[j+1] == '.' {
g0[j+1] = '#'
}
return 1
}
}
if g0[i] == '.' {
g0[i] = '#'
}
if g1[i] == '.' {
g1[i] = '#'
}
return 2
}
cal := func() int {
for i := 1; i < l; i++ {
if g0[i]+g1[i] == 3 || g0[i-1]+g0[i] == 3 || g1[i-1]+g1[i] == 3 {
return 1e5
}
}
o, p, t := 0, 0, -1
for i := 1; i < l; i++ {
if g0[i] == 1 || g1[i] == 1 {
if t == 2 {
o += cal1(i, p)
}
p, t = i, 1
} else if g0[i] == 2 || g1[i] == 2 {
if t == 1 {
o += cal1(i, p)
}
p, t = i, 2
}
}
return o
}
for i := 1; i < l-1; i++ {
switch g0[i] {
case 'S', 'P':
g0[i] = 1
case 'C':
g0[i] = 2
}
switch g1[i] {
case 'S', 'P':
g1[i] = 1
case 'C':
g1[i] = 2
}
}
o := cal()
g0, g1 = g0t, g1t
for i := 1; i < l-1; i++ {
switch g0[i] {
case 'S':
g0[i] = 1
case 'C', 'P':
g0[i] = 2
}
switch g1[i] {
case 'S':
g1[i] = 1
case 'C', 'P':
g1[i] = 2
}
}
o = min(o, cal())
if o == 1e5 {
return -1
}
return o
}
