AtCoder NoviStepsを埋めてみる(26) 幅優先探索 1Q

AtCoder NoviStepsを埋めてみる(26) 幅優先探索 2Qの続きです。今回も幅優先探索（BFS）です。やや難しめの問題に挑戦します。

D – Reachability Query 2

問題の概要

N 頂点 M 辺の有向グラフが与えられる。
頂点には色がつけられていて最初はすべて白色である。
Q 個のクエリが与えられるので順番に処理せよ。
クエリ 1：頂点 v を黒色にする。
クエリ 2：頂点 v から辺を辿って黒色の頂点に到達可能かどうか判定する。

クエリ 2 が来るたびに頂点 v から黒い頂点にたどり着けるか調べていると時間がかかります。そこで辺を逆向きにしてクエリ 1 が来たらそこからたどりつける頂点をすべて黒で塗ります。この方法だと黒く塗られた頂点は以降は探索対象から外れるため処理にかかる時間を短縮できます。

class Program
{
    // 最短経路長を求めるのではなく訪問済みかどうかのみを調べる幅優先探索をおこなう
    static void Bfs(List<int>[] G, int start, bool[] seen)
    {
        // これがないとスターグラフ（いわゆるウニ）のとき TLE する場合がある
        if (seen[start])
            return;

        Queue<int> q = new Queue<int>();

        seen[start] = true;
        q.Enqueue(start);

        while (q.Count > 0)
        {
            int cur = q.Dequeue();
            foreach (var next in G[cur])
            {
                if (!seen[next])
                {
                    seen[next] = true;
                    q.Enqueue(next);
                }
            }
        }
    }

    static void Main()
    {
        int[] nm = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
        int N = nm[0];
        int M = nm[1];

        List<int>[] rG = new List<int>[N];
        for (int i = 0; i < N; i++)
            rG[i] = new List<int>();

        for (int i = 0; i < M; i++)
        {
            int[] xy = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            int x = xy[0] - 1;
            int y = xy[1] - 1;
            rG[y].Add(x);
        }

        int Q = int.Parse(Console.ReadLine());
        bool[] seen = new bool[N];

        List<string> ans = new List<string>();
        for (int i = 0; i < Q; i++)
        {
            int[] query = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            int t = query[0];
            int v = query[1] - 1;
            if (t == 1)
                Bfs(rG, v, seen);
            if (t == 2)
                ans.Add(seen[v] ? "Yes" : "No");
        }

        foreach (string str in ans)
            Console.WriteLine(str);
    }
}

class Program

{

// 最短経路長を求めるのではなく訪問済みかどうかのみを調べる幅優先探索をおこなう

static void Bfs(List<int>[] G, int start, bool[] seen)

{

// これがないとスターグラフ（いわゆるウニ）のとき TLE する場合がある

if (seen[start])

return;

Queue<int> q = new Queue<int>();

seen[start] = true;

q.Enqueue(start);

while (q.Count > 0)

{

int cur = q.Dequeue();

foreach (var next in G[cur])

{

if (!seen[next])

{

seen[next] = true;

q.Enqueue(next);

}

static void Main()

{

int[] nm = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int N = nm[0];

int M = nm[1];

List<int>[] rG = new List<int>[N];

for (int i = 0; i < N; i++)

rG[i] = new List<int>();

for (int i = 0; i < M; i++)

{

int[] xy = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int x = xy[0] - 1;

int y = xy[1] - 1;

rG[y].Add(x);

}

int Q = int.Parse(Console.ReadLine());

bool[] seen = new bool[N];

List<string> ans = new List<string>();

for (int i = 0; i < Q; i++)

{

int[] query = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int t = query[0];

int v = query[1] - 1;

if (t == 1)

Bfs(rG, v, seen);

if (t == 2)

ans.Add(seen[v] ? "Yes" : "No");

}

foreach (string str in ans)

Console.WriteLine(str);

}

D – XOR Shortest Walk

問題の概要

N 頂点 M 辺の有向グラフが与えられる。
辺 i は頂点 A[i] から頂点 B[i] への重み W[i] の有向辺である。
頂点 1 から頂点 N への walk のうち、walk に含まれる辺の重みのビット単位 XOR の最小値を求めよ。

単純な頂点 1 から頂点 N への最短経路長を問う問題ではなく、辺の重みの XOR を計算しなければなりません。このような場合、どうすればよいのでしょうか？

こんなときに使えるのが「頂点倍化」です。頂点倍化とは付随する状態について新たに点を作って、その状態遷移について辺を貼ることです。

頂点 1 から各頂点への walk について walk に含まれる辺の重みのビット単位は 1024 通り考えられます。そこで各頂点の訪問済みフラグを 1024 個定義します。

あとは幅優先探索をして seen[N – 1, i] = true である最小の i を出力すればこれが解となります。

class Program
{
    static void Main()
    {
        int[] nm = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
        int N = nm[0];
        int M = nm[1];

        List<(int, int)>[] G = new List<(int, int)>[N];
        for (int i = 0; i < N; i++)
            G[i] = new List<(int, int)>();

        for (int i = 0; i < M; i++)
        {
            int[] abw = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            int a = abw[0] - 1;
            int b = abw[1] - 1;
            int w = abw[2];
            G[a].Add((b, w));
        }

        Queue<(int, int)> q = new Queue<(int, int)>();
        q.Enqueue((0, 0));

        bool[,] seen = new bool[N, 1024];
        seen[0, 0] = true;

        while (q.Count > 0)
        {
            var cur = q.Dequeue();
            int cur_idx = cur.Item1;
            int cur_val = cur.Item2;
            foreach (var next in G[cur_idx])
            {
                int next_idx = next.Item1;
                int next_val = cur_val ^ next.Item2;

                if (!seen[next_idx, next_val])
                {
                    seen[next_idx, next_val] = true;
                    q.Enqueue((next_idx, next_val));
                }
            }
        }

        int ans = -1;
        for (int i = 0; i < 1024; i++)
        {
            if (seen[N - 1, i])
            {
                ans = i;
                break;
            }
        }
        Console.WriteLine(ans);
    }
}

class Program

{

static void Main()

{

int[] nm = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int N = nm[0];

int M = nm[1];

List<(int, int)>[] G = new List<(int, int)>[N];

for (int i = 0; i < N; i++)

G[i] = new List<(int, int)>();

for (int i = 0; i < M; i++)

{

int[] abw = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int a = abw[0] - 1;

int b = abw[1] - 1;

int w = abw[2];

G[a].Add((b, w));

}

Queue<(int, int)> q = new Queue<(int, int)>();

q.Enqueue((0, 0));

bool[,] seen = new bool[N, 1024];

seen[0, 0] = true;

while (q.Count > 0)

{

var cur = q.Dequeue();

int cur_idx = cur.Item1;

int cur_val = cur.Item2;

foreach (var next in G[cur_idx])

{

int next_idx = next.Item1;

int next_val = cur_val ^ next.Item2;

if (!seen[next_idx, next_val])

{

seen[next_idx, next_val] = true;

q.Enqueue((next_idx, next_val));

}

int ans = -1;

for (int i = 0; i < 1024; i++)

{

if (seen[N - 1, i])

{

ans = i;

break;

}

Console.WriteLine(ans);

}

D – Snaky Walk

問題の概要

H 行 W 列のグリッドがある。’S’ から ‘G’ まで移動することはできるだろうか？
ただし障害物マスやグリッドの外に移動することはできず、また縦移動と横移動を 1 回ずつ交互に行わなければならない。
可能ならば移動回数の最小値を求めよ。

「縦移動と横移動を 1 回ずつ交互におこなう」ということなので、マスを白黒の市松模様に塗り、「白マスは上下のみ、黒マスは左右のみ移動可」とする場合と白マスと黒マスの役割を入れ替えた場合の 2 パターンを考えます。

グリッド上の幅優先探索をおこない最短経路長を比較します。小さいほうが出力すべき解です。

class Program
{
    static void Main()
    {
        int[] hw = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
        int H = hw[0];
        int W = hw[1];

        bool[,] grid = new bool[H, W];
        int sr = 0, sc = 0, gr = 0, gc = 0;
        for (int r = 0; r < H; r++)
        {
            char[] vs = Console.ReadLine().ToArray();
            for (int c = 0; c < W; c++)
            {
                grid[r, c] = vs[c] != '#';
                if (vs[c] == 'S')
                {
                    sr = r;
                    sc = c;
                }
                if (vs[c] == 'G')
                {
                    gr = r;
                    gc = c;
                }
            }
        }

        int ans = Math.Min(Bfs(true), Bfs(false));
        if (ans == int.MaxValue)
            ans = -1;
        Console.WriteLine(ans);

        int Bfs(bool b)
        {
            Queue<(int, int)> q = new Queue<(int, int)>();
            q.Enqueue((sr, sc));

            int[,] dists = new int[H, W];
            for (int r = 0; r < H; r++)
            {
                for (int c = 0; c < W; c++)
                    dists[r, c] = int.MaxValue;
            }
            dists[sr, sc] = 0;

            (int, int)[] diffs1 = [(1, 0), (-1, 0)];
            (int, int)[] diffs2 = [(0, 1), (0, -1)];

            while (q.Count > 0)
            {
                var cur = q.Dequeue();
                int r = cur.Item1;
                int c = cur.Item2;
                int v = dists[r, c];

                (int, int)[] diffs = [];

                if ((r + c) % 2 == (b ? 0 : 1))
                    diffs = diffs1;
                else
                    diffs = diffs2;

                foreach (var diff in diffs)
                {
                    int nr = r + diff.Item1;
                    int nc = c + diff.Item2;
                    if (nr < 0 || nr >= H || nc < 0 || nc >= W || !grid[nr, nc])
                        continue;

                    if (dists[nr, nc] > v + 1)
                    {
                        dists[nr, nc] = v + 1;
                        q.Enqueue((nr, nc));
                    }
                }
            }
            return dists[gr, gc];
        }
    }
}

class Program

{

static void Main()

{

int[] hw = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int H = hw[0];

int W = hw[1];

bool[,] grid = new bool[H, W];

int sr = 0, sc = 0, gr = 0, gc = 0;

for (int r = 0; r < H; r++)

{

char[] vs = Console.ReadLine().ToArray();

for (int c = 0; c < W; c++)

{

grid[r, c] = vs[c] != '#';

if (vs[c] == 'S')

{

sr = r;

sc = c;

}

if (vs[c] == 'G')

{

gr = r;

gc = c;

}

int ans = Math.Min(Bfs(true), Bfs(false));

if (ans == int.MaxValue)

ans = -1;

Console.WriteLine(ans);

int Bfs(bool b)

{

Queue<(int, int)> q = new Queue<(int, int)>();

q.Enqueue((sr, sc));

int[,] dists = new int[H, W];

for (int r = 0; r < H; r++)

{

for (int c = 0; c < W; c++)

dists[r, c] = int.MaxValue;

}

dists[sr, sc] = 0;

(int, int)[] diffs1 = [(1, 0), (-1, 0)];

(int, int)[] diffs2 = [(0, 1), (0, -1)];

while (q.Count > 0)

{

var cur = q.Dequeue();

int r = cur.Item1;

int c = cur.Item2;

int v = dists[r, c];

(int, int)[] diffs = [];

if ((r + c) % 2 == (b ? 0 : 1))

diffs = diffs1;

else

diffs = diffs2;

foreach (var diff in diffs)

{

int nr = r + diff.Item1;

int nc = c + diff.Item2;

if (nr < 0 || nr >= H || nc < 0 || nc >= W || !grid[nr, nc])

continue;

if (dists[nr, nc] > v + 1)

{

dists[nr, nc] = v + 1;

q.Enqueue((nr, nc));

}

return dists[gr, gc];

}

D – Repeatedly Repainting

問題の概要

H 行 W 列のグリッドがあり、各マスは白か黒で塗られている。
以下の操作を 10^100 回おこなう。操作を終えた後に各マスが何色で塗られているか求めよ。
（操作）
操作前に黒く塗られているマスは、白く塗り替える。
操作前に白く塗られているマスは、そのマスに隣接（8方向）するマスで黒で塗られているものが存在するときだけ黒く塗り替える。

1 回以上の操作を行って得られるマス目について、黒く塗られたマスは、隣接する白く塗られたマスを持ちます。問題の条件より黒く塗られたマスはそれ以降交互に色を変えることになります。

そこで 1 回だけ操作を行い、その後に初めてマスが黒く塗られるタイミング（の偶奇）が各マスについてわかればこの問題を解くことができます。

あとは多始点型の幅優先探索をして 1 回だけ操作をおこなった状態における黒マスからの最短経路長を求めればよいです。奇数であれば ‘#’, 偶数であれば ‘.’ です。黒マスが存在しない場合はすべて ‘.’ です。

class Program
{
    static void Main()
    {
        int[] hw = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
        int H = hw[0];
        int W = hw[1];

        char[,] grid = new char[H, W];
        for (int r = 0; r < H; r++)
        {
            char[] vs = Console.ReadLine().ToArray();
            for (int c = 0; c < W; c++)
                grid[r, c] = vs[c];
        }

        (int, int)[] diffs = [(0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1)];

        List<(int, int)> starts = new List<(int, int)>();
        for (int r = 0; r < H; r++)
        {
            for (int c = 0; c < W; c++)
            {
                char ch = '.';
                if (grid[r, c] == '#')
                    ch = '.';
                else
                {
                    foreach (var diff in diffs)
                    {
                        int nr = r + diff.Item1;
                        int nc = c + diff.Item2;
                        if (nr < 0 || nr >= H || nc < 0 || nc >= W)
                            continue;
                        if(grid[nr, nc] == '#')
                            ch = '#';
                    }
                }
                if(ch == '#')
                    starts.Add((r, c));
            }
        }

        Queue<(int, int)> q = new Queue<(int, int)>();
        int[,] dists = new int[H, W];
        for (int r = 0; r < H; r++)
        {
            for (int c = 0; c < W; c++)
                dists[r, c] = 10000000;
        }

        foreach (var start in starts)
        {
            q.Enqueue((start.Item1, start.Item2));
            dists[start.Item1, start.Item2] = 0;
        }

        while (q.Count > 0)
        {
            var cur = q.Dequeue();
            int r = cur.Item1;
            int c = cur.Item2;
            int v = dists[r, c];

            foreach (var diff in diffs)
            {
                int nr = r + diff.Item1;
                int nc = c + diff.Item2;
                if (nr < 0 || nr >= H || nc < 0 || nc >= W)
                    continue;

                if (dists[nr, nc] > v + 1)
                {
                    dists[nr, nc] = v + 1;
                    q.Enqueue((nr, nc));
                }
            }
        }

        for (int r = 0; r < H; r++)
        {
            char[] vs = new char[W];
            for (int c = 0; c < W; c++)
                vs[c] = dists[r, c] % 2 == 1 ? '#' : '.';
            Console.WriteLine(new string(vs));
        }
    }
}

class Program

{

static void Main()

{

int[] hw = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int H = hw[0];

int W = hw[1];

char[,] grid = new char[H, W];

for (int r = 0; r < H; r++)

{

char[] vs = Console.ReadLine().ToArray();

for (int c = 0; c < W; c++)

grid[r, c] = vs[c];

}

(int, int)[] diffs = [(0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1)];

List<(int, int)> starts = new List<(int, int)>();

for (int r = 0; r < H; r++)

{

for (int c = 0; c < W; c++)

{

char ch = '.';

if (grid[r, c] == '#')

ch = '.';

else

{

foreach (var diff in diffs)

{

int nr = r + diff.Item1;

int nc = c + diff.Item2;

if (nr < 0 || nr >= H || nc < 0 || nc >= W)

continue;

if(grid[nr, nc] == '#')

ch = '#';

}

if(ch == '#')

starts.Add((r, c));

}

Queue<(int, int)> q = new Queue<(int, int)>();

int[,] dists = new int[H, W];

for (int r = 0; r < H; r++)

{

for (int c = 0; c < W; c++)

dists[r, c] = 10000000;

}

foreach (var start in starts)

{

q.Enqueue((start.Item1, start.Item2));

dists[start.Item1, start.Item2] = 0;

}

while (q.Count > 0)

{

var cur = q.Dequeue();

int r = cur.Item1;

int c = cur.Item2;

int v = dists[r, c];

foreach (var diff in diffs)

{

int nr = r + diff.Item1;

int nc = c + diff.Item2;

if (nr < 0 || nr >= H || nc < 0 || nc >= W)

continue;

if (dists[nr, nc] > v + 1)

{

dists[nr, nc] = v + 1;

q.Enqueue((nr, nc));

}

for (int r = 0; r < H; r++)

{

char[] vs = new char[W];

for (int c = 0; c < W; c++)

vs[c] = dists[r, c] % 2 == 1 ? '#' : '.';

Console.WriteLine(new string(vs));

}

D – Go Straight

問題の概要

H 行 W 列のグリッドがある。
‘#’ が書かれているマスに立ち入ることはできない。
‘o’ が書かれているマスでは直前の移動と同じ方向に移動しなければならない。
‘x’ が書かれているマスでは直前の移動と同じ方向に移動することはできない。
上記の条件で ‘S’ から ‘G’ まで移動することはできるだろうか？
可能ならば移動方法をひとつ出力せよ。

‘o’ や ‘x’ マスにおいては直前の移動方向が問題になるので訪問済みフラグを 4 つ用意します。Queue に格納する情報がひとつ増えますが、あとは通常の幅優先探索と同じです。

class Program
{
    static void Main()
    {
        int[] hw = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
        int H = hw[0];
        int W = hw[1];

        char[,] grid = new char[H, W];
        int sr = 0, sc = 0, gr = 0, gc = 0;
        for (int r = 0; r < H; r++)
        {
            char[] vs = Console.ReadLine().ToArray();
            for (int c = 0; c < W; c++)
            {
                grid[r, c] = vs[c];
                if (vs[c] == 'S')
                {
                    sr = r;
                    sc = c;
                }
                if (vs[c] == 'G')
                {
                    gr = r;
                    gc = c;
                }
            }
        }

        // 移動方向 right, left, down, up
        (int, int)[] diffs = [(0, 1), (0, -1), (1, 0), (-1, 0)];

        Queue<(int, int, int)> q = new Queue<(int, int, int)>();
        int[,,] dists = new int[H, W, 4];
        (int, int, int)[,,] froms = new (int, int, int)[H, W, 4];
        for (int r = 0; r < H; r++)
        {
            for (int c = 0; c < W; c++)
            {
                dists[r, c, 0] = int.MaxValue;
                dists[r, c, 1] = int.MaxValue;
                dists[r, c, 2] = int.MaxValue;
                dists[r, c, 3] = int.MaxValue;
            }
        }

        q.Enqueue((sr, sc, 0));
        dists[sr, sc, 0] = 0;
        froms[sr, sc, 0] = (-1, -1, -1);

        while (q.Count > 0)
        {
            var cur = q.Dequeue();
            int r = cur.Item1;
            int c = cur.Item2;
            int z = cur.Item3;
            int v = dists[r, c, z];

            for (int nz = 0; nz < 4; nz++)
            {
                if (grid[r, c] == 'o')
                {
                    if (nz != z) // 直進しかできない
                        continue;
                }
                if (grid[r, c] == 'x')
                {
                    if (nz == z) // 直進はできない
                        continue;
                }

                int nr = r + diffs[nz].Item1;
                int nc = c + diffs[nz].Item2;
                if (nr < 0 || nr >= H || nc < 0 || nc >= W)
                    continue;

                if (grid[nr, nc] == '#')
                    continue;

                if (dists[nr, nc, nz] > v + 1)
                {
                    dists[nr, nc, nz] = v + 1;
                    froms[nr, nc, nz] = (r, c, z);
                    q.Enqueue((nr, nc, nz));
                }
            }
        }

        List<int> res = new List<int>();
        for (int i = 0; i < 4; i++)
            res.Add(dists[gr, gc, i]);

        int min = res.Min();
        if (min == int.MaxValue)
        {
            Console.WriteLine("No");
            return;
        }

        Console.WriteLine("Yes");

        // 経路復元（ゴールからスタート地点へ逆にたどっていく）
        int last_z = res.IndexOf(min);
        int last_r = gr;
        int last_c = gc;

        List<(int, int, int)> path = new List<(int, int, int)> ();
        path.Add((last_r, last_c, last_z));

        while (true)
        {
            var tp = froms[last_r, last_c, last_z];
            last_r = tp.Item1;
            last_c = tp.Item2;
            last_z = tp.Item3;
            if (last_r == -1)
                break;

            path.Add(tp);
        }

        path.Reverse();

        // 各ステップの現在位置の変化から移動方向がわかる
        List<char> ans = new List<char>();
        for (int i = 0; i < path.Count - 1; i++)
        {
            if (path[i].Item1 < path[i + 1].Item1)
                ans.Add('D');
            if (path[i].Item1 > path[i + 1].Item1)
                ans.Add('U');
            if (path[i].Item2 < path[i + 1].Item2)
                ans.Add('R');
            if (path[i].Item2 > path[i + 1].Item2)
                ans.Add('L');
        }
        Console.WriteLine(new string(ans.ToArray()));
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

class Program

{

static void Main()

{

int[] hw = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int H = hw[0];

int W = hw[1];

char[,] grid = new char[H, W];

int sr = 0, sc = 0, gr = 0, gc = 0;

for (int r = 0; r < H; r++)

{

char[] vs = Console.ReadLine().ToArray();

for (int c = 0; c < W; c++)

{

grid[r, c] = vs[c];

if (vs[c] == 'S')

{

sr = r;

sc = c;

}

if (vs[c] == 'G')

{

gr = r;

gc = c;

}

// 移動方向 right, left, down, up

(int, int)[] diffs = [(0, 1), (0, -1), (1, 0), (-1, 0)];

Queue<(int, int, int)> q = new Queue<(int, int, int)>();

int[,,] dists = new int[H, W, 4];

(int, int, int)[,,] froms = new (int, int, int)[H, W, 4];

for (int r = 0; r < H; r++)

{

for (int c = 0; c < W; c++)

{

dists[r, c, 0] = int.MaxValue;

dists[r, c, 1] = int.MaxValue;

dists[r, c, 2] = int.MaxValue;

dists[r, c, 3] = int.MaxValue;

}

q.Enqueue((sr, sc, 0));

dists[sr, sc, 0] = 0;

froms[sr, sc, 0] = (-1, -1, -1);

while (q.Count > 0)

{

var cur = q.Dequeue();

int r = cur.Item1;

int c = cur.Item2;

int z = cur.Item3;

int v = dists[r, c, z];

for (int nz = 0; nz < 4; nz++)

{

if (grid[r, c] == 'o')

{

if (nz != z) // 直進しかできない

continue;

}

if (grid[r, c] == 'x')

{

if (nz == z) // 直進はできない

continue;

}

int nr = r + diffs[nz].Item1;

int nc = c + diffs[nz].Item2;

if (nr < 0 || nr >= H || nc < 0 || nc >= W)

continue;

if (grid[nr, nc] == '#')

continue;

if (dists[nr, nc, nz] > v + 1)

{

dists[nr, nc, nz] = v + 1;

froms[nr, nc, nz] = (r, c, z);

q.Enqueue((nr, nc, nz));

}

List<int> res = new List<int>();

for (int i = 0; i < 4; i++)

res.Add(dists[gr, gc, i]);

int min = res.Min();

if (min == int.MaxValue)

{

Console.WriteLine("No");

return;

}

Console.WriteLine("Yes");

// 経路復元（ゴールからスタート地点へ逆にたどっていく）

int last_z = res.IndexOf(min);

int last_r = gr;

int last_c = gc;

List<(int, int, int)> path = new List<(int, int, int)> ();

path.Add((last_r, last_c, last_z));

while (true)

{

var tp = froms[last_r, last_c, last_z];

last_r = tp.Item1;

last_c = tp.Item2;

last_z = tp.Item3;

if (last_r == -1)

break;

path.Add(tp);

}

path.Reverse();

// 各ステップの現在位置の変化から移動方向がわかる

List<char> ans = new List<char>();

for (int i = 0; i < path.Count - 1; i++)

{

if (path[i].Item1 < path[i + 1].Item1)

ans.Add('D');

if (path[i].Item1 > path[i + 1].Item1)

ans.Add('U');

if (path[i].Item2 < path[i + 1].Item2)

ans.Add('R');

if (path[i].Item2 > path[i + 1].Item2)

ans.Add('L');

}

Console.WriteLine(new string(ans.ToArray()));

}

D – Go Stone Puzzle

問題の概要

N + 2 個のマスが横一列に並んでいて、マス 1 からマス N には白または黒の石が 1 個ずつ置かれている。
「石が 2 個並んでいる箇所を選び、その 2 個の石を順序を保って空きマスに移す」という操作を繰り返して A の状態から B の状態へ移行することはできるだろうか？可能なら操作回数の最小値を出力せよ。

A にふたつ並んだ空きマスを 1 文字として追加した場合、この文字列が取りうる場合の数は (N + 1)! / (B! * W!) です。これは最大でも 51,480 通りにしかなりません。なので幅優先探索をすることで B と一致させるための最短手数を求めることができます（下記コードではふたつ並んだ空きマスを “..” の 2 文字で表している）。

class Program
{
    static void Main()
    {
        int N = int.Parse(Console.ReadLine());
        string S = Console.ReadLine();
        string T = Console.ReadLine();

        S += "..";
        T += "..";

        List<string> GetNextStrings(string s)
        {
            List<string> res = new List<string>();
            int idx = s.IndexOf("..");
            for (int i = 0; i < s.Length - 1; i++)
            {
                int idx_1 = i;
                int idx_2 = i + 1;
                if (Math.Abs(idx - idx_1) <= 1)
                    continue;

                char[] t = s.ToArray();
                t[idx] = s[idx_1];
                t[idx + 1] = s[idx_2];
                t[idx_1] = '.';
                t[idx_2] = '.';
                res.Add(new string(t));
            }
            return res;
        }

        Queue<string> q = new Queue<string>();
        q.Enqueue(S);

        Dictionary<string, int> dic = new Dictionary<string, int>();
        dic.Add(S, 0);

        while (q.Count > 0)
        {
            string cur = q.Dequeue();
            int cnt = dic[cur];
            List<string> nexts = GetNextStrings(cur);
            foreach (string next in nexts)
            {
                if (!dic.ContainsKey(next))
                {
                    dic.Add(next, cnt + 1);
                    q.Enqueue(next);
                }
            }
        }

        if (dic.ContainsKey(T))
            Console.WriteLine(dic[T]);
        else
            Console.WriteLine(-1);
    }
}

class Program

{

static void Main()

{

int N = int.Parse(Console.ReadLine());

string S = Console.ReadLine();

string T = Console.ReadLine();

S += "..";

T += "..";

List<string> GetNextStrings(string s)

{

List<string> res = new List<string>();

int idx = s.IndexOf("..");

for (int i = 0; i < s.Length - 1; i++)

{

int idx_1 = i;

int idx_2 = i + 1;

if (Math.Abs(idx - idx_1) <= 1)

continue;

char[] t = s.ToArray();

t[idx] = s[idx_1];

t[idx + 1] = s[idx_2];

t[idx_1] = '.';

t[idx_2] = '.';

res.Add(new string(t));

}

return res;

}

Queue<string> q = new Queue<string>();

q.Enqueue(S);

Dictionary<string, int> dic = new Dictionary<string, int>();

dic.Add(S, 0);

while (q.Count > 0)

{

string cur = q.Dequeue();

int cnt = dic[cur];

List<string> nexts = GetNextStrings(cur);

foreach (string next in nexts)

{

if (!dic.ContainsKey(next))

{

dic.Add(next, cnt + 1);

q.Enqueue(next);

}

if (dic.ContainsKey(T))

Console.WriteLine(dic[T]);

else

Console.WriteLine(-1);

}

D – Grid and Magnet

問題の概要

H 行 W 列のグリッドがある。
‘#’ が書かれているマスは磁石であり立ち入ることができないだけでなく、その隣に移動してしまうと吸い付いてしまい、そこから動くことができなくなる。
磁石が置かれていないマスの中における、マスの自由度の最大値を求めよ。

単純な訪問済みフラグだと磁石の隣への移動を考えるときに困るので工夫をします。

訪問済みフラグを bool 型ではなく int 型にして探索開始点によって 1 以上の異なる値で埋めることにします。探索開始点がすでに 1 以上の値のときはそこからは探索を開始しません。探索中に異なる値があった場合は上書きします。各探索開始点からもっとも更新回数が多かったものが求めるべき解となります。

class Program
{
    static void Main()
    {
        int[] hw = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
        int H = hw[0];
        int W = hw[1];

        char[,] grid = new char[H, W];
        for (int r = 0; r < H; r++)
        {
            char[] vs = Console.ReadLine().ToArray();
            for (int c = 0; c < W; c++)
                grid[r, c] = vs[c];
        }

        int[,] seen = new int[H, W];
        (int, int)[] diffs = [(1, 0), (-1, 0), (0, 1), (0, -1)];

        int ans = 0;
        for (int r = 0; r < H; r++)
        {
            for (int c = 0; c < W; c++)
            {
                if (grid[r, c] == '.' && seen[r, c] == 0)
                {
                    int res = Bfs(r, c, r * W + c + 1);
                    ans = Math.Max(ans, res);
                }
            }
        }
        Console.WriteLine(ans);

        int Bfs(int sr, int sc, int val)
        {
            Queue<(int, int)> q = new Queue<(int, int)>();
            q.Enqueue((sr, sc));
            seen[sr, sc] = val;
            int cnt = 1; // (sr, sc) を起点に動ける回数を数える

            while (q.Count > 0)
            {
                var cur = q.Dequeue();
                int r = cur.Item1;
                int c = cur.Item2;
                bool no_move = false;
                for (int i = 0; i < 4; i++)
                {
                    int nr = r + diffs[i].Item1;
                    int nc = c + diffs[i].Item2;
                    if (nr < 0 || nr >= H || nc < 0 || nc >= W)
                        continue;

                    if (grid[nr, nc] == '#') // 隣が磁石なのでここからは動けない
                    {
                        no_move = true;
                        break;
                    }
                }

                if (no_move)
                    continue;

                for (int i = 0; i < 4; i++)
                {
                    int nr = r + diffs[i].Item1;
                    int nc = c + diffs[i].Item2;
                    if (nr < 0 || nr >= H || nc < 0 || nc >= W)
                        continue;

                    if (seen[nr, nc] != val)
                    {
                        seen[nr, nc] = val;
                        q.Enqueue((nr, nc));
                        cnt++;
                    }
                }
            }
            return cnt;
        }
    }
}

class Program

{

static void Main()

{

int[] hw = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int H = hw[0];

int W = hw[1];

char[,] grid = new char[H, W];

for (int r = 0; r < H; r++)

{

char[] vs = Console.ReadLine().ToArray();

for (int c = 0; c < W; c++)

grid[r, c] = vs[c];

}

int[,] seen = new int[H, W];

(int, int)[] diffs = [(1, 0), (-1, 0), (0, 1), (0, -1)];

int ans = 0;

for (int r = 0; r < H; r++)

{

for (int c = 0; c < W; c++)

{

if (grid[r, c] == '.' && seen[r, c] == 0)

{

int res = Bfs(r, c, r * W + c + 1);

ans = Math.Max(ans, res);

}

Console.WriteLine(ans);

int Bfs(int sr, int sc, int val)

{

Queue<(int, int)> q = new Queue<(int, int)>();

q.Enqueue((sr, sc));

seen[sr, sc] = val;

int cnt = 1; // (sr, sc) を起点に動ける回数を数える

while (q.Count > 0)

{

var cur = q.Dequeue();

int r = cur.Item1;

int c = cur.Item2;

bool no_move = false;

for (int i = 0; i < 4; i++)

{

int nr = r + diffs[i].Item1;

int nc = c + diffs[i].Item2;

if (nr < 0 || nr >= H || nc < 0 || nc >= W)

continue;

if (grid[nr, nc] == '#') // 隣が磁石なのでここからは動けない

{

no_move = true;

break;

}

if (no_move)

continue;

for (int i = 0; i < 4; i++)

{

int nr = r + diffs[i].Item1;

int nc = c + diffs[i].Item2;

if (nr < 0 || nr >= H || nc < 0 || nc >= W)

continue;

if (seen[nr, nc] != val)

{

seen[nr, nc] = val;

q.Enqueue((nr, nc));

cnt++;

}

return cnt;

}

D – Medicines on Grid

問題の概要

H 行 W 列のグリッドがある。
‘#’ が書かれているマスに立ち入ることはできない。
上下左右に隣り合う空きマスへエネルギーを 1 消費して移動することができる。
エネルギーが 0 の状態で移動することはできない。
グリッドには合計で N 個の薬がある。i 番目の薬は空きマス (R[i] ,C[i]) にあり、使う使わないを選ぶことができる。使うと薬はなくなりエネルギーが E[i] に変更される（必ずしもエネルギーが増えるとは限らない）。
‘S’ から ‘G’ まで移動することはできるだろうか？

まず薬 i からほかの薬やゴールまで移動できるか調べます。最短経路長が E[i] 以内であれば移動可能です。頂点を N + 1 個用意して薬 i から薬 j まで移動可能であれば、頂点 i から頂点 j へ辺を張ります。また薬 i からゴールまで移動可能であれば、頂点 i から頂点 N へ辺を張ります。

スタート地点に薬がない場合はエネルギーが 0 なので移動できず “No” が解となります。そうでない場合はスタート地点に相当する頂点から頂点 N までたどり着ける場合は “Yes” そうでない場合は “No” です。

class Program
{
    static void GridBfs(bool[,] grid, int sr, int sc, int[,] dists)
    {
        int h = grid.GetLength(0);
        int w = grid.GetLength(1);

        Queue<int> qR = new Queue<int>();
        Queue<int> qC = new Queue<int>();

        qR.Enqueue(sr);
        qC.Enqueue(sc);
        dists[sr, sc] = 0;

        (int, int)[] diffs = [(1, 0), (-1, 0), (0, 1), (0, -1)];
        while (qR.Count > 0)
        {
            int r = qR.Dequeue();
            int c = qC.Dequeue();
            int v = dists[r, c];
            for (int i = 0; i < 4; i++)
            {
                int nr = r + diffs[i].Item1;
                int nc = c + diffs[i].Item2;
                if (nr < 0 || nr >= h || nc < 0 || nc >= w || !grid[nr, nc])
                    continue;
                if (dists[nr, nc] > v + 1)
                {
                    dists[nr, nc] = v + 1;
                    qR.Enqueue(nr);
                    qC.Enqueue(nc);
                }
            }
        }
    }

    static void Bfs(List<int>[] G, int start, int[] dists)
    {
        Queue<int> q = new Queue<int>();

        dists[start] = 0;
        q.Enqueue(start);

        while (q.Count > 0)
        {
            int cur = q.Dequeue();
            foreach (var next in G[cur])
            {
                if (dists[next] > dists[cur] + 1)
                {
                    dists[next] = dists[cur] + 1;
                    q.Enqueue(next);
                }
            }
        }
    }

    static void Main()
    {
        int[] hw = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
        int H = hw[0];
        int W = hw[1];

        bool[,] grid = new bool[H, W];
        int sr = 0, sc = 0, gr = 0, gc = 0;
        for (int r = 0; r < H; r++)
        {
            char[] vs = Console.ReadLine().ToArray();
            for (int c = 0; c < W; c++)
            {
                grid[r, c] = vs[c] != '#';
                if (vs[c] == 'S')
                {
                    sr = r;
                    sc = c;
                }
                if (vs[c] == 'T')
                {
                    gr = r;
                    gc = c;
                }
            }
        }

        int N = int.Parse(Console.ReadLine());

        int[] R = new int[N + 1];
        int[] C = new int[N + 1];
        int[] E = new int[N + 1];
        int start = -1;
        for (int i = 0; i < N; i++)
        {
            int[] rce = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            R[i] = rce[0] - 1;
            C[i] = rce[1] - 1;
            E[i] = rce[2];
            if(R[i] == sr && C[i] == sc)
                start = i;
        }
        R[N] = gr;
        C[N] = gc;

        // 薬 i から別の薬 + ゴールへ移動可能か調べる
        List<int>[] G = new List<int>[N + 1];
        for (int i = 0; i <= N; i++)
            G[i] = new List<int>();

        for (int i = 0; i < N; i++)
        {
            int[,] dists = new int[H, W];
            for (int r = 0; r < H; r++)
            {
                for (int c = 0; c < W; c++)
                    dists[r, c] = int.MaxValue;
            }

            GridBfs(grid, R[i], C[i], dists);

            for (int j = 0; j <= N; j++)
            {
                if (i != j && dists[R[j], C[j]] <= E[i])
                    G[i].Add(j);
            }
        }

        // start から N（ゴール）へ移動可能か調べる
        if (start != -1)
        {
            int[] dists2 = new int[N + 1];
            Array.Fill(dists2, int.MaxValue);
            Bfs(G, start, dists2);
            Console.WriteLine(dists2[N] < int.MaxValue ? "Yes" : "No");
        }
        else
            Console.WriteLine("No");
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

class Program

{

static void GridBfs(bool[,] grid, int sr, int sc, int[,] dists)

{

int h = grid.GetLength(0);

int w = grid.GetLength(1);

Queue<int> qR = new Queue<int>();

Queue<int> qC = new Queue<int>();

qR.Enqueue(sr);

qC.Enqueue(sc);

dists[sr, sc] = 0;

(int, int)[] diffs = [(1, 0), (-1, 0), (0, 1), (0, -1)];

while (qR.Count > 0)

{

int r = qR.Dequeue();

int c = qC.Dequeue();

int v = dists[r, c];

for (int i = 0; i < 4; i++)

{

int nr = r + diffs[i].Item1;

int nc = c + diffs[i].Item2;

if (nr < 0 || nr >= h || nc < 0 || nc >= w || !grid[nr, nc])

continue;

if (dists[nr, nc] > v + 1)

{

dists[nr, nc] = v + 1;

qR.Enqueue(nr);

qC.Enqueue(nc);

}

static void Bfs(List<int>[] G, int start, int[] dists)

{

Queue<int> q = new Queue<int>();

dists[start] = 0;

q.Enqueue(start);

while (q.Count > 0)

{

int cur = q.Dequeue();

foreach (var next in G[cur])

{

if (dists[next] > dists[cur] + 1)

{

dists[next] = dists[cur] + 1;

q.Enqueue(next);

}

static void Main()

{

int[] hw = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int H = hw[0];

int W = hw[1];

bool[,] grid = new bool[H, W];

int sr = 0, sc = 0, gr = 0, gc = 0;

for (int r = 0; r < H; r++)

{

char[] vs = Console.ReadLine().ToArray();

for (int c = 0; c < W; c++)

{

grid[r, c] = vs[c] != '#';

if (vs[c] == 'S')

{

sr = r;

sc = c;

}

if (vs[c] == 'T')

{

gr = r;

gc = c;

}

int N = int.Parse(Console.ReadLine());

int[] R = new int[N + 1];

int[] C = new int[N + 1];

int[] E = new int[N + 1];

int start = -1;

for (int i = 0; i < N; i++)

{

int[] rce = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

R[i] = rce[0] - 1;

C[i] = rce[1] - 1;

E[i] = rce[2];

if(R[i] == sr && C[i] == sc)

start = i;

}

R[N] = gr;

C[N] = gc;

// 薬 i から別の薬 + ゴールへ移動可能か調べる

List<int>[] G = new List<int>[N + 1];

for (int i = 0; i <= N; i++)

G[i] = new List<int>();

for (int i = 0; i < N; i++)

{

int[,] dists = new int[H, W];

for (int r = 0; r < H; r++)

{

for (int c = 0; c < W; c++)

dists[r, c] = int.MaxValue;

}

GridBfs(grid, R[i], C[i], dists);

for (int j = 0; j <= N; j++)

{

if (i != j && dists[R[j], C[j]] <= E[i])

G[i].Add(j);

}

// start から N（ゴール）へ移動可能か調べる

if (start != -1)

{

int[] dists2 = new int[N + 1];

Array.Fill(dists2, int.MaxValue);

Bfs(G, start, dists2);

Console.WriteLine(dists2[N] < int.MaxValue ? "Yes" : "No");

}

else

Console.WriteLine("No");

}

D – Synchronized Players

問題の概要

N 行 N 列のグリッドがある。グリッド上にふたりのプレイヤーがいる。
上下左右のいずれかの方向を決め、各プレイヤーをその方向に隣接するマスへの移動可能なら移動させる。
このような操作を繰り返してふたりのプレイヤーを同じマスに集めることはできるだろうか？
可能であればそのために必要な操作回数の最小値を求めよ。

ふたりのプレイヤーの位置情報で幅優先探索をすればよいです。ふたりのプレイヤーの位置の組み合わせは N^4 通りあります。なので時間計算量も O(N^4) ですが、N の最大値は 60、実行時間制限は 4 秒なので充分間に合います。

class Program
{
    static void Main()
    {
        int N = int.Parse(Console.ReadLine());

        char[,] grid = new char[N, N];
        List<(int, int)> P = new List<(int, int)>();
        for (int r = 0; r < N; r++)
        {
            char[] vs = Console.ReadLine().ToArray();
            for (int c = 0; c < N; c++)
            {
                grid[r, c] = vs[c] == '#' ? '#' : '.';
                if (vs[c] == 'P')
                    P.Add((r, c));
            }
        }

        (int, int)[] diffs = [(1, 0), (-1, 0), (0, 1), (0, -1)];

        Queue<(int, int, int, int)> q = new Queue<(int, int, int, int)>();

        q.Enqueue((P[0].Item1, P[0].Item2, P[1].Item1, P[1].Item2));

        int[,,,] dists = new int[N, N, N, N];

        for (int a = 0; a < N; a++)
        {
            for (int b = 0; b < N; b++)
            {
                for (int c = 0; c < N; c++)
                {
                    for (int d = 0; d < N; d++)
                        dists[a, b, c, d] = int.MaxValue;
                }
            }
        }

        dists[P[0].Item1, P[0].Item2, P[1].Item1, P[1].Item2] = 0;

        while (q.Count > 0)
        {
            var cur = q.Dequeue();
            int r0 = cur.Item1;
            int c0 = cur.Item2;
            int r1 = cur.Item3;
            int c1 = cur.Item4;
            int cnt = dists[r0, c0, r1, c1];

            for (int i = 0; i < 4; i++)
            {
                int nr0 = r0 + diffs[i].Item1;
                int nc0 = c0 + diffs[i].Item2;
                if (nr0 < 0 || nr0 >= N || nc0 < 0 || nc0 >= N || grid[nr0, nc0] == '#')
                {
                    nr0 = r0; // 移動できないのでその場に留まる
                    nc0 = c0;
                }

                int nr1 = r1 + diffs[i].Item1;
                int nc1 = c1 + diffs[i].Item2;
                if (nr1 < 0 || nr1 >= N || nc1 < 0 || nc1 >= N || grid[nr1, nc1] == '#')
                {
                    nr1 = r1; // 移動できないのでその場に留まる
                    nc1 = c1;
                }

                if (dists[nr0, nc0, nr1, nc1] > cnt + 1)
                {
                    dists[nr0, nc0, nr1, nc1] = cnt + 1;
                    q.Enqueue((nr0, nc0, nr1, nc1));
                }
            }
        }

        int ans = int.MaxValue;
        for (int r = 0; r < N; r++)
        {
            for (int c = 0; c < N; c++)
                ans = Math.Min(dists[r, c, r, c], ans);
        }

        if (ans == int.MaxValue)
            ans = -1;

        Console.WriteLine(ans);
    }
}

class Program

{

static void Main()

{

int N = int.Parse(Console.ReadLine());

char[,] grid = new char[N, N];

List<(int, int)> P = new List<(int, int)>();

for (int r = 0; r < N; r++)

{

char[] vs = Console.ReadLine().ToArray();

for (int c = 0; c < N; c++)

{

grid[r, c] = vs[c] == '#' ? '#' : '.';

if (vs[c] == 'P')

P.Add((r, c));

}

(int, int)[] diffs = [(1, 0), (-1, 0), (0, 1), (0, -1)];

Queue<(int, int, int, int)> q = new Queue<(int, int, int, int)>();

q.Enqueue((P[0].Item1, P[0].Item2, P[1].Item1, P[1].Item2));

int[,,,] dists = new int[N, N, N, N];

for (int a = 0; a < N; a++)

{

for (int b = 0; b < N; b++)

{

for (int c = 0; c < N; c++)

{

for (int d = 0; d < N; d++)

dists[a, b, c, d] = int.MaxValue;

}

dists[P[0].Item1, P[0].Item2, P[1].Item1, P[1].Item2] = 0;

while (q.Count > 0)

{

var cur = q.Dequeue();

int r0 = cur.Item1;

int c0 = cur.Item2;

int r1 = cur.Item3;

int c1 = cur.Item4;

int cnt = dists[r0, c0, r1, c1];

for (int i = 0; i < 4; i++)

{

int nr0 = r0 + diffs[i].Item1;

int nc0 = c0 + diffs[i].Item2;

if (nr0 < 0 || nr0 >= N || nc0 < 0 || nc0 >= N || grid[nr0, nc0] == '#')

{

nr0 = r0; // 移動できないのでその場に留まる

nc0 = c0;

}

int nr1 = r1 + diffs[i].Item1;

int nc1 = c1 + diffs[i].Item2;

if (nr1 < 0 || nr1 >= N || nc1 < 0 || nc1 >= N || grid[nr1, nc1] == '#')

{

nr1 = r1; // 移動できないのでその場に留まる

nc1 = c1;

}

if (dists[nr0, nc0, nr1, nc1] > cnt + 1)

{

dists[nr0, nc0, nr1, nc1] = cnt + 1;

q.Enqueue((nr0, nc0, nr1, nc1));

}

int ans = int.MaxValue;

for (int r = 0; r < N; r++)

{

for (int c = 0; c < N; c++)

ans = Math.Min(dists[r, c, r, c], ans);

}

if (ans == int.MaxValue)

ans = -1;

Console.WriteLine(ans);

}

E – Prerequisites

問題の概要

1 から N までの番号がついた N 冊の本がある。
本 i には C[i] 冊の前提となる本があり、そのうち j 冊目は本 P[i,j] であり、これらをすべて読む必要がある。
本 1 を読むためにそれ以外に読まなければならない本の番号を読むべき順に出力せよ。

N 個の頂点を用意して頂点 i から頂点 P[i,j] に向けて辺を張ります。これは本 i を読むためには本 P[i,j] をすべて読まなければならないことを意味しています。そして頂点 1 から幅優先探索をしたときに訪問した頂点が読むべき本の集合となります。

それらを読むべき順に出力する方法ですが、頂点 P[i,j] から頂点 i に向けて辺を張ったグラフを構築してトポロジカルソートすればよいです。ただし、新しくグラフを構築するのではなく、読むべき本の集合を求めるために使ったグラフをトポロジカルソートして逆順にしたほうが速いです。このなかから集合に含まれているものだけを出力します。

class Program
{
    static void Main()
    {
        int N = int.Parse(Console.ReadLine());

        List<int>[] G = new List<int>[N];
        int[] counts = new int[N];
        for (int i = 0; i < N; i++)
        {
            G[i] = new List<int>();
            int[] vs = Console.ReadLine().Split().Skip(1).Select(_ => int.Parse(_) - 1).ToArray();
            foreach (int next in vs)
            {
                G[i].Add(next);
                counts[next]++;
            }
        }

        // 本 1 から幅優先探索をしてたどりつくことができた本は読まなければならない本である。
        Queue<int> q = new Queue<int>();
        q.Enqueue(0);

        bool[] seen = new bool[N];
        seen[0] = true;

        while (q.Count > 0)
        {
            int cur = q.Dequeue();
            foreach (int next in G[cur])
            {
                if (!seen[next])
                {
                    seen[next] = true;
                    q.Enqueue(next);
                }
            }
        }

        // 読まなければならない本を読む順番に並べる。トポロジカルソートの逆順から読むべき本のみ取り出す。
        List<int> ans = new List<int>();
        for (int i = 0; i < N; i++)
        {
            if (counts[i] == 0)
            {
                q.Enqueue(i);
                if (seen[i] && i != 0)
                    ans.Add(i + 1);
            }
        }

        while (q.Count > 0)
        {
            int cur = q.Dequeue();
            foreach (int next in G[cur])
            {
                counts[next]--;
                if (counts[next] == 0)
                {
                    q.Enqueue(next);
                    if(seen[next])
                        ans.Add(next + 1);
                }
            }
        }

        ans.Reverse();
        Console.WriteLine(string.Join(" ", ans));
    }
}

class Program

{

static void Main()

{

int N = int.Parse(Console.ReadLine());

List<int>[] G = new List<int>[N];

int[] counts = new int[N];

for (int i = 0; i < N; i++)

{

G[i] = new List<int>();

int[] vs = Console.ReadLine().Split().Skip(1).Select(_ => int.Parse(_) - 1).ToArray();

foreach (int next in vs)

{

G[i].Add(next);

counts[next]++;

}

// 本 1 から幅優先探索をしてたどりつくことができた本は読まなければならない本である。

Queue<int> q = new Queue<int>();

q.Enqueue(0);

bool[] seen = new bool[N];

seen[0] = true;

while (q.Count > 0)

{

int cur = q.Dequeue();

foreach (int next in G[cur])

{

if (!seen[next])

{

seen[next] = true;

q.Enqueue(next);

}

// 読まなければならない本を読む順番に並べる。トポロジカルソートの逆順から読むべき本のみ取り出す。

List<int> ans = new List<int>();

for (int i = 0; i < N; i++)

{

if (counts[i] == 0)

{

q.Enqueue(i);

if (seen[i] && i != 0)

ans.Add(i + 1);

}

while (q.Count > 0)

{

int cur = q.Dequeue();

foreach (int next in G[cur])

{

counts[next]--;

if (counts[next] == 0)

{

q.Enqueue(next);

if(seen[next])

ans.Add(next + 1);

}

ans.Reverse();

Console.WriteLine(string.Join(" ", ans));

}

E – Nearest Black Vertex

問題の概要

N 個の頂点と M 本の辺からなる単純連結無向グラフが与えられる。
「頂点 P[i] と「黒で塗られた頂点のうち頂点 P[i] からの距離が最小であるもの」の距離がちょうど D[i] である」という条件を満たす 1 個以上の頂点が黒で塗られているグラフを示せ。

以下の方法が思いつきます。

最初はすべての頂点を黒で塗る。
頂点 P[i] から距離が D[i] 未満のものを白で塗り直す。

ただし、これだけでは落ちるケースがあります。頂点 P[0] から距離が D[0] 未満のものを白で塗り直したときには頂点 P[0] から距離がちょうど D[0] であるものが存在したけど、頂点 P[1] から距離が D[1] 未満のものを白で塗り直したときに頂点 P[0] から距離がちょうど D[0] であるものがすべて白で塗り直されてなくなっている場合があるからです。なので K 個の処理が終わった後、頂点 P[i] から距離が D[i] と同じものが本当に存在するか確認する処理が必要です（十分性の検証）。

class Program
{
    static void Bfs(List<int>[] G, int start, int[] dists)
    {
        Queue<int> q = new Queue<int>();

        dists[start] = 0;
        q.Enqueue(start);

        while (q.Count > 0)
        {
            int cur = q.Dequeue();
            foreach (var next in G[cur])
            {
                if (dists[next] > dists[cur] + 1)
                {
                    dists[next] = dists[cur] + 1;
                    q.Enqueue(next);
                }
            }
        }
    }

    static void Main()
    {
        int[] nm = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
        int N = nm[0];
        int M = nm[1];

        List<int>[] G = new List<int>[N];
        for (int i = 0; i < N; i++)
            G[i] = new List<int>();

        for (int i = 0; i < M; i++)
        {
            int[] uv = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            int u = uv[0] - 1;
            int v = uv[1] - 1;
            G[u].Add(v);
            G[v].Add(u);
        }

        int K = int.Parse(Console.ReadLine());
        int[] P = new int[K];
        int[] D = new int[K];
        for (int i = 0; i < K; i++)
        {
            int[] pd = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            P[i] = pd[0] - 1;
            D[i] = pd[1];
        }

        // 最初はすべての頂点を黒で塗る。
        // 頂点 P[i] から距離が D[i] 未満のものを白で塗り直す。
        char[] isBlacks = new char[N];
        Array.Fill(isBlacks, '1');

        for (int i = 0; i < K; i++)
        {
            int[] dists = new int[N];
            Array.Fill(dists, int.MaxValue);
            Bfs(G, P[i], dists);

            for (int j = 0; j < N; j++)
            {
                if (dists[j] < D[i])
                    isBlacks[j] = '0';
            }
        }

        // 上記の処理をしたあと本当に条件を満たしているか確認（十分性の確認）
        bool ng = false;
        for (int i = 0; i < K; i++)
        {
            int[] dists = new int[N];
            Array.Fill(dists, int.MaxValue);
            Bfs(G, P[i], dists);

            bool ok = false;
            for (int j = 0; j < N; j++)
            {
                if (dists[j] == D[i] && isBlacks[j] == '1')
                    ok = true;
            }
            if (!ok)
            {
                ng = true;
                break;
            }
        }
        if (!ng && isBlacks.Any(_ => _ == '1'))
        {
            Console.WriteLine("Yes");
            Console.WriteLine(new string(isBlacks));
        }
        else
            Console.WriteLine("No");
    }
}

class Program

{

static void Bfs(List<int>[] G, int start, int[] dists)

{

Queue<int> q = new Queue<int>();

dists[start] = 0;

q.Enqueue(start);

while (q.Count > 0)

{

int cur = q.Dequeue();

foreach (var next in G[cur])

{

if (dists[next] > dists[cur] + 1)

{

dists[next] = dists[cur] + 1;

q.Enqueue(next);

}

static void Main()

{

int[] nm = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int N = nm[0];

int M = nm[1];

List<int>[] G = new List<int>[N];

for (int i = 0; i < N; i++)

G[i] = new List<int>();

for (int i = 0; i < M; i++)

{

int[] uv = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int u = uv[0] - 1;

int v = uv[1] - 1;

G[u].Add(v);

G[v].Add(u);

}

int K = int.Parse(Console.ReadLine());

int[] P = new int[K];

int[] D = new int[K];

for (int i = 0; i < K; i++)

{

int[] pd = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

P[i] = pd[0] - 1;

D[i] = pd[1];

}

// 最初はすべての頂点を黒で塗る。

// 頂点 P[i] から距離が D[i] 未満のものを白で塗り直す。

char[] isBlacks = new char[N];

Array.Fill(isBlacks, '1');

for (int i = 0; i < K; i++)

{

int[] dists = new int[N];

Array.Fill(dists, int.MaxValue);

Bfs(G, P[i], dists);

for (int j = 0; j < N; j++)

{

if (dists[j] < D[i])

isBlacks[j] = '0';

}

// 上記の処理をしたあと本当に条件を満たしているか確認（十分性の確認）

bool ng = false;

for (int i = 0; i < K; i++)

{

int[] dists = new int[N];

Array.Fill(dists, int.MaxValue);

Bfs(G, P[i], dists);

bool ok = false;

for (int j = 0; j < N; j++)

{

if (dists[j] == D[i] && isBlacks[j] == '1')

ok = true;

}

if (!ok)

{

ng = true;

break;

}

if (!ng && isBlacks.Any(_ => _ == '1'))

{

Console.WriteLine("Yes");

Console.WriteLine(new string(isBlacks));

}

else

Console.WriteLine("No");

}

E – Swap Places

問題の概要

N 頂点 M 辺の単純無向グラフがあり、すべての頂点は赤か青のいずれか一方で塗られている。
高橋君が頂点 1 に、青木君が頂点 N にいる。
2 人が同時に、今いる頂点に隣接している頂点のいずれか 1 個に移動する。
ただし、高橋君の移動先の頂点の色と、青木君の移動先の頂点の色は異なる必要がある。
高橋君が頂点 N に、青木君が頂点 1 にいる状態にできるだろうか？
可能である場合は必要な行動回数の最小値を答えよ。

class Program
{
    static void Main()
    {
        int T = int.Parse(Console.ReadLine());

        for (int i = 0; i < T; i++)
        {
            Solve();
        }

        void Solve()
        {
            int[] nm = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            int N = nm[0];
            int M = nm[1];
            int[] C = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

            List<int>[] G = new List<int>[N];
            for (int i = 0; i < N; i++)
                G[i] = new List<int>();

            for (int i = 0; i < M; i++)
            {
                int[] uv = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
                int u = uv[0] - 1;
                int v = uv[1] - 1;
                G[u].Add(v);
                G[v].Add(u);
            }

            Queue<(int, int)> q = new Queue<(int, int)> ();
            q.Enqueue((0, N - 1));

            int[,] dists = new int[N, N];
            for (int i = 0; i < N; i++)
            {
                for (int j = 0; j < N; j++)
                    dists[i, j] = int.MaxValue;
            }
            dists[0, N - 1] = 0;

            while (q.Count > 0)
            {
                var cur = q.Dequeue();
                int cur1 = cur.Item1;
                int cur2 = cur.Item2;
                int v = dists[cur1, cur2];

                List<(int, int)> nexts = new List<(int, int)>();
                foreach (int next1 in G[cur1])
                {
                    foreach (int next2 in G[cur2])
                    {
                        if (C[next1] != C[next2])
                            nexts.Add((next1, next2));
                    }
                }
                foreach (var next in nexts)
                {
                    if (dists[next.Item1, next.Item2] > v + 1)
                    {
                        dists[next.Item1, next.Item2] = v + 1;
                        q.Enqueue((next.Item1, next.Item2));
                    }
                }
            }
            int ans = dists[N - 1, 0];
            Console.WriteLine(ans < int.MaxValue ? ans : -1);
        }
    }
}

class Program

{

static void Main()

{

int T = int.Parse(Console.ReadLine());

for (int i = 0; i < T; i++)

{

Solve();

}

void Solve()

{

int[] nm = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int N = nm[0];

int M = nm[1];

int[] C = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

List<int>[] G = new List<int>[N];

for (int i = 0; i < N; i++)

G[i] = new List<int>();

for (int i = 0; i < M; i++)

{

int[] uv = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int u = uv[0] - 1;

int v = uv[1] - 1;

G[u].Add(v);

G[v].Add(u);

}

Queue<(int, int)> q = new Queue<(int, int)> ();

q.Enqueue((0, N - 1));

int[,] dists = new int[N, N];

for (int i = 0; i < N; i++)

{

for (int j = 0; j < N; j++)

dists[i, j] = int.MaxValue;

}

dists[0, N - 1] = 0;

while (q.Count > 0)

{

var cur = q.Dequeue();

int cur1 = cur.Item1;

int cur2 = cur.Item2;

int v = dists[cur1, cur2];

List<(int, int)> nexts = new List<(int, int)>();

foreach (int next1 in G[cur1])

{

foreach (int next2 in G[cur2])

{

if (C[next1] != C[next2])

nexts.Add((next1, next2));

}

foreach (var next in nexts)

{

if (dists[next.Item1, next.Item2] > v + 1)

{

dists[next.Item1, next.Item2] = v + 1;

q.Enqueue((next.Item1, next.Item2));

}

int ans = dists[N - 1, 0];

Console.WriteLine(ans < int.MaxValue ? ans : -1);

}

AtCoder NoviStepsを埋めてみる(26) 幅優先探索 1Q

D – Reachability Query 2

D – XOR Shortest Walk

D – Snaky Walk

D – Repeatedly Repainting

D – Go Straight

D – Go Stone Puzzle

D – Grid and Magnet

D – Medicines on Grid

D – Synchronized Players

E – Prerequisites

E – Nearest Black Vertex

E – Swap Places

鳩でも分かるC#管理人からのお願い

コメントについて

管理人のモチベーションアップのために

コメントをどうぞ