SRM625D1Med BlockTheBlockPuzzle
面倒
問題概要(原文)
$N \times M$ のグリッドがある．$1 \times 1 \times 2$ のブロックを転がして移動させ，ゴールのマスに底面が $1 \times 1$ になるように置きたい．転がすときのルールは以下の通り
- 底面が $1 \times 1$ のとき，好きな $4$ 方向に転がせる
- 底面が $1 \times 2$ のとき，底面が $1 \times 1$ になるような方向に転がせる
始点の候補はいくつかあり，好きなところから選べる．
ブロックを転がすときに底面が完全に穴に埋まってはならない． 何回空マスを穴にすれば，ゴールできないようにできるか？
考察
最小カットを求めたい気持ちになる． ブロックは底面が $1 \times 1$ の状態から $1 \times 1$ の状態になるためには $(x,y) \rightarrow (x \pm 3,0), (x,y \pm 3)$ のような遷移しかない．
以下のような辺を張って最小カットを求めればそれが答え
- スーパーソースから，ゴールにたどり着けるような出発地点の入力側に容量 $\infty$
- 出発地点の入力側から出発地点の出力側へ容量 $\infty$
- ゴールの入力側からゴールの出力側へ容量 $\infty$
- ゴールの出力からシンクへ容量 $\infty$
- 空きマスの入力から空きマスの出力側へ容量 $1$
- 穴でないマス $(x,y)$ の出力側と穴でないマス $(x \pm3, y), (x, y \pm 3)$ の入力側に以下のルールで辺を張る
- $2$ つのマス間にスタート地点があるならば容量 $\infty$
- $2$ つのマス間にある穴のマスの数を $k$ として容量 $2 - k$
ソースコード
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using Debug = System.Diagnostics.Debug;
using StringBuilder = System.Text.StringBuilder;
public class BlockTheBlockPuzzle
{
public int minimumHoles(string[] board)
{
var n = board.Length;
var m = board[0].Length;
var G = Enumerate(2 * n * m + 2, x => new List<Edge<int>>());
var src = 2 * n * m;
var sink = src + 1;
int[] dx = { 1, 0, -1, 0 };
int[] dy = { 0, 1, 0, -1 };
int px = -1, py = -1;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (board[i][j] == '$') { px = i; py = j; }
for (int i = 0; i < n; i++)
{
if (Math.Abs(i - px) % 3 != 0) continue;
for (int j = 0; j < m; j++)
{
if (Math.Abs(j - py) % 3 != 0) continue;
switch (board[i][j])
{
case 'b':
G.AddDirectedEdge(src, i * m + j, 100000);
G.AddDirectedEdge(i * m + j, n * m + i * m + j, 100000);
break;
case '$':
G.AddDirectedEdge(n * m + i * m + j, sink, 100000);
G.AddDirectedEdge(i * m + j, n * m + i * m + j, 100000);
break;
case '.':
G.AddDirectedEdge(i * m + j, n * m + i * m + j, 1);
break;
case 'H': break;
default:
break;
}
for (int d = 0; d < 4; d++)
{
var nx = i + dx[d] * 3;
var ny = j + dy[d] * 3;
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
var a = board[i][j];
var b = board[nx][ny];
if (a == 'H' || b == 'H') continue;
var bcnt = 0;
var hcnt = 0;
for (int nnx = Math.Min(i, nx); nnx <= Math.Max(i, nx); nnx++)
for (int nny = Math.Min(j, ny); nny <= Math.Max(j, ny); nny++)
{
if (board[nnx][nny] == 'b') bcnt++;
if (board[nnx][nny] == 'H') hcnt++;
}
if (a == 'b') bcnt--;
if (b == 'b') bcnt--;
var cap = 2 - hcnt;
if (bcnt > 0) cap = 100000;
G.AddDirectedEdge(n * m + i * m + j, nx * m + ny, cap);
}
}
}
var ans = Flow.GetMaxFlow(G, src, sink);
if (ans > 1000) return -1;
return ans;
}
static public T[] Enumerate<T>(int n, Func<int, T> f) { var a = new T[n]; for (int i = 0; i < n; ++i) a[i] = f(i); return a; }
static public void Swap<T>(ref T a, ref T b) { var tmp = a; a = b; b = tmp; }
// CUT begin
public int Naive_Test(string[] board)
{
return 0;
}
// CUT end
}
static public class EnumerableEX
{
static public string AsString(this IEnumerable<char> e) { return new string(e.ToArray()); }
static public string AsJoinedString<T>(this IEnumerable<T> e, string s = " ") { return string.Join(s, e); }
}
// CUT begin
public partial class Tester: AbstractTester
{
static public T[] Enumerate<T>(int n, Func<int, T> f) { var a = new T[n]; for (int i = 0; i < n; ++i) a[i] = f(i); return a; }
public Random rand = new Random(0);
public void OnInit()
{
}
}
// CUT end
#region Edge
public class Edge<T>
{
public int to, rev;
public T cap;
public Edge(int t, int r, T _cap) { to = t; rev = r; cap = _cap; }
public override string ToString() { return string.Format("{0}: Capacity {1}", to, cap); }
}
#endregion
#region AddEdge
static public partial class Flow
{
static public void AddDirectedEdge(this List<Edge<int>>[] G, int from, int to, int cap)
{
G[from].Add(new Edge<int>(to, G[to].Count, cap));
G[to].Add(new Edge<int>(from, G[from].Count - 1, 0));
}
static public void AddUndirectedEdge(this List<Edge<int>>[] G, int from, int to, int cap)
{
G[from].Add(new Edge<int>(to, G[to].Count, cap));
G[to].Add(new Edge<int>(from, G[from].Count - 1, cap));
}
static public void AddDirectedEdge(this List<Edge<long>>[] G, int from, int to, long cap)
{
G[from].Add(new Edge<long>(to, G[to].Count, cap));
G[to].Add(new Edge<long>(from, G[from].Count - 1, 0));
}
static public void AddUndirectedEdge(this List<Edge<long>>[] G, int from, int to, long cap)
{
G[from].Add(new Edge<long>(to, G[to].Count, cap));
G[to].Add(new Edge<long>(from, G[from].Count - 1, cap));
}
}
#endregion
//MaxFlow
#region Dinic
static public partial class Flow
{
static public int GetMaxFlow(List<Edge<int>>[] G, int s, int t, int INF = -1)
{
var n = G.Length;
var level = new int[n];
var iter = new int[n];
Action<int> bfs = p =>
{
Array.Clear(level, 0, n);
var q = new Queue<int>();
level[s] = 1;
q.Enqueue(s);
while (q.Any())
{
var v = q.Dequeue();
foreach (var e in G[v])
if (e.cap > 0 && level[e.to] == 0)
{
level[e.to] = level[v] + 1;
q.Enqueue(e.to);
}
}
};
Func<int, int, int, int> dfs = null;
dfs = (v, u, f) =>
{
if (v == t) return f;
for (; iter[v] < G[v].Count; iter[v]++)
{
var e = G[v][iter[v]];
if (e.cap <= 0 || level[v] >= level[e.to]) continue;
var d = dfs(e.to, u, Math.Min(f, e.cap));
if (d <= 0) continue;
e.cap -= d;
G[e.to][e.rev].cap += d;
return d;
}
return 0;
};
var flow = 0;
if (INF == -1)
{
while (true)
{
bfs(s);
if (level[t] == 0) return flow;
Array.Clear(iter, 0, iter.Length);
int f;
while ((f = dfs(s, t, 1 << 30)) > 0) { flow += f; }
}
}
else
{
while (INF > 0)
{
bfs(s);
if (level[t] == 0) return flow;
Array.Clear(iter, 0, iter.Length);
int f;
while ((f = dfs(s, t, 1 << 30)) > 0) { flow += f; INF -= f; }
}
return flow;
}
}
}
#endregion
コメント
- 辺を張るのが面倒
