ARC040D カクカク塗り
これはすごい．
問題概要(原文)
$N \times N$ のグリッドが与えられる．幾つかのマスは通行禁止である． スタートマスが与えられ，$1$ 歩進むごとに $90^{\circ}$ 方向転換をする． このような条件のときにハミルトンパスはあるか判定せよ．
考察
ハミルトンパスの判定なので基本的な方針としてなにか良い性質があるか考える必要がある． $90^{\circ}$ 方向転換を繰り返す，というのが本質的に重要である．
このとき，$1$ 歩進むというのは上下，あるいは左右に辺を $1$ 本貼る操作であり，各マスからは縦，あるいは横に $1$ 本ずつ辺が生えている． さらに壁側のマスは生える方向が定まり，連鎖的に行，列における辺の方向が定まる． ここで，始点および終点というのは，上下，あるいは左右の辺のどちらかしか生えていないことに注意しないといけない． また，以下のようなケースも注意が必要(始点終点は別にあると思って)
####..###
#......##
#...#...#
######..#
..##
..##
##..
##..
上は，偶数個あって，連結できそうだけど壁が邪魔でできない． 下は，全体が連結にならない． ちゃんとつないで判定する必要がある．
結局，ハミルトンパスを持つための必要十分条件は以下の通りである．
- どの行，列も偶数個空きマスがある
- 上で示したように辺で連鎖的に連結したとき，空きマスだけからなるグラフが全体として連結
ここで終点の候補が $O(N^2)$ 個あって大変に思えるが，どの列，どの行を選ぶか，という候補が実は少ないため，終点の候補は $O(N)$ 個程度．
全体として $O(N^3 \alpha(N))$
ソースコード
using System;
using System.Linq;
using System.Collections.Generic;
using Debug = System.Diagnostics.Debug;
using StringBuilder = System.Text.StringBuilder;
using System.Numerics;
using Point = System.Numerics.Complex;
using Number = System.Int64;
using C = System.Int32;
namespace Program
{
public class Solver
{
public void Solve()
{
var n = sc.Integer();
var A = Enumerate(n, _ => sc.Char(n));
var R = new int[n];
var C = new int[n];
var x = -1; var y = -1;
var cnt = 1;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
{
if (A[i][j] == '.')
{
cnt++;
R[i]++;
C[j]++;
}
if (A[i][j] == 's')
{
R[i]++; C[j]++;
x = i; y = j;
}
}
Debug.WriteLine(cnt);
var ok = false;
for (int d = 0; d < 2; d++)
{
if (d == 0) { R[x]--; A[x][y] = '|'; }
else { C[y]--; A[x][y] = '-'; }
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
{
if (A[i][j] == '.')
{
for (int e = 0; e < 2; e++)
{
if (e == 0) { R[i]--; A[i][j] = '|'; }
else { C[j]--; A[i][j] = '-'; }
var go = true;
for (int k = 0; k < n; k++)
if (R[k] % 2 == 1 || C[k] % 2 == 1) { go = false; break; }
if (go && f(n, A, x, y, d, i, j, e, cnt))
{
IO.Printer.Out.WriteLine("POSSIBLE");
return;
}
if (e == 0) R[i]++;
else C[j]++;
A[i][j] = '.';
}
}
}
if (d == 0) R[x]++;
else C[y]++;
}
if (ok) IO.Printer.Out.WriteLine("POSSIBLE");
else IO.Printer.Out.WriteLine("IMPOSSIBLE");
}
bool f(int n, char[][] A, int x, int y, int z, int a, int b, int c, int cnt)
{
Debug.WriteLine("{3} {0} {1} {2}", a, b, c, z);
var s = new DisjointSet(n * n);
for (int i = 0; i < n; i++)
for (int j = 0; j < n;)
{
if (A[i][j] == '.' || A[i][j] == '-')
{
if (j + 1 >= n) return false;
if (A[i][j] == '.' || A[i][j] == '-') s.Unite((i * n) + j, (i * n) + j + 1);
else return false;
j += 2;
}
else j++;
}
for (int j = 0; j < n; j++)
for (int i = 0; i < n;)
{
if (A[i][j] == '.' || A[i][j] == '|')
{
if (i + 1 >= n) return false;
if (A[i][j] == '.' || A[i][j] == '|') s.Unite((i * n) + j, (i + 1) * n + j);
else return false;
i += 2;
}
else i++;
}
return s.Size(x * n + y) == cnt;
}
public IO.StreamScanner sc = new IO.StreamScanner(Console.OpenStandardInput());
static 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; }
}
}
#region main
static class Ex
{
static public string AsString(this IEnumerable<char> ie) { return new string(System.Linq.Enumerable.ToArray(ie)); }
static public string AsJoinedString<T>(this IEnumerable<T> ie, string st = " ") { return string.Join(st, ie); }
static public void Main()
{
var solver = new Program.Solver();
solver.Solve();
Program.IO.Printer.Out.Flush();
}
}
#endregion
#region Ex
namespace Program.IO
{
using System.IO;
using System.Text;
using System.Globalization;
public class Printer: StreamWriter
{
static Printer() { Out = new Printer(Console.OpenStandardOutput()) { AutoFlush = false }; }
public static Printer Out { get; set; }
public override IFormatProvider FormatProvider { get { return CultureInfo.InvariantCulture; } }
public Printer(System.IO.Stream stream) : base(stream, new UTF8Encoding(false, true)) { }
public Printer(System.IO.Stream stream, Encoding encoding) : base(stream, encoding) { }
public void Write<T>(string format, T[] source) { base.Write(format, source.OfType<object>().ToArray()); }
public void WriteLine<T>(string format, T[] source) { base.WriteLine(format, source.OfType<object>().ToArray()); }
}
public class StreamScanner
{
public StreamScanner(Stream stream) { str = stream; }
public readonly Stream str;
private readonly byte[] buf = new byte[1024];
private int len, ptr;
public bool isEof = false;
public bool IsEndOfStream { get { return isEof; } }
private byte read()
{
if (isEof) return 0;
if (ptr >= len) { ptr = 0; if ((len = str.Read(buf, 0, 1024)) <= 0) { isEof = true; return 0; } }
return buf[ptr++];
}
public char Char() { byte b = 0; do b = read(); while ((b < 33 || 126 < b) && !isEof); return (char)b; }
public string Scan()
{
var sb = new StringBuilder();
for (var b = Char(); b >= 33 && b <= 126; b = (char)read())
sb.Append(b);
return sb.ToString();
}
public string ScanLine()
{
var sb = new StringBuilder();
for (var b = Char(); b != '\n'; b = (char)read())
if (b == 0) break;
else if (b != '\r') sb.Append(b);
return sb.ToString();
}
public long Long()
{
if (isEof) return long.MinValue;
long ret = 0; byte b = 0; var ng = false;
do b = read();
while (b != 0 && b != '-' && (b < '0' || '9' < b));
if (b == 0) return long.MinValue;
if (b == '-') { ng = true; b = read(); }
for (; true; b = read())
{
if (b < '0' || '9' < b)
return ng ? -ret : ret;
else ret = ret * 10 + b - '0';
}
}
public int Integer() { return (isEof) ? int.MinValue : (int)Long(); }
public double Double() { var s = Scan(); return s != "" ? double.Parse(s, CultureInfo.InvariantCulture) : double.NaN; }
private T[] enumerate<T>(int n, Func<T> f)
{
var a = new T[n];
for (int i = 0; i < n; ++i) a[i] = f();
return a;
}
public char[] Char(int n) { return enumerate(n, Char); }
public string[] Scan(int n) { return enumerate(n, Scan); }
public double[] Double(int n) { return enumerate(n, Double); }
public int[] Integer(int n) { return enumerate(n, Integer); }
public long[] Long(int n) { return enumerate(n, Long); }
}
}
#endregion
#region DisjointSet
public class DisjointSet
{
int[] par;
byte[] rank;
public DisjointSet(int n)
{
par = new int[n];
for (int i = 0; i < n; i++)
par[i] = -1;
rank = new byte[n];
}
public int this[int id]
{
get
{
if ((par[id] < 0)) return id;
return par[id] = this[par[id]];
}
}
public bool Unite(int x, int y)
{
x = this[x]; y = this[y];
if (x == y) return false;
if (rank[x] < rank[y])
{
par[y] += par[x];
par[x] = y;
}
else
{
par[x] += par[y];
par[y] = x;
if (rank[x] == rank[y])
rank[x]++;
}
return true;
}
public int Size(int x) { return -par[this[x]]; }
public bool IsUnited(int x, int y) { return this[x] == this[y]; }
}
#endregion
コメント
- 驚くべきad-hoc
- 連鎖的に決まっていくし面白い
