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

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

E – Transitivity

問題の概要

N 頂点 M 辺の単純有向グラフが与えられる。
このグラフが次の条件を満たす状態にするために最小で何回操作を行う必要があるかを求めよ。
（操作）相異なる頂点 x, y であって頂点 x から頂点 y への有向辺が存在しないようなものを選ぶ。そして、頂点 x から頂点 y への有向辺を追加する。
（条件）相異なる頂点 a, b, c すべてについて、頂点 a から頂点 b への有向辺と頂点 b から頂点 c への有向辺がともに存在するならば頂点 a から頂点 c への有向辺も存在する。

この操作を繰り返すことは頂点 x, y が連結ならば頂点 x, y 間に辺を張ることと同じです。このことに気がつけば、すべての頂点についてその頂点からたどり着ける頂点の個数を数えることで、操作が完了したときに存在する辺の総数がわかります。追加すべき辺の最小値はここから最初から存在する辺の数である M を引いた数です。

class Program
{
    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);
        }

        int cnt = 0;
        for (int i = 0; i < N; i++)
        {
            Queue<int> q = new Queue<int>();
            bool[] seen = new bool[N];

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

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

                    seen[next] = true;
                    q.Enqueue(next);
                    cnt++;
                }
            }
        }
        Console.WriteLine(cnt - M);
    }
}

class Program

{

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);

}

int cnt = 0;

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

{

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

bool[] seen = new bool[N];

q.Enqueue(i);

seen[i] = true;

while (q.Count > 0)

{

int cur = q.Dequeue();

foreach (int next in G[cur])

{

if (seen[next])

continue;

seen[next] = true;

q.Enqueue(next);

cnt++;

}

Console.WriteLine(cnt - M);

}

E – Small d and k

問題の概要

N 頂点 M 辺の単純無向グラフがある（各頂点の次数は 3 以下）。
次のクエリに答えよ。
クエリ：頂点 x[i] との距離が k[i] 以下であるような頂点の番号の総和を求めよ。

各頂点の次数は 3 以下であり、調べなければならない距離も 3 以下であることから頂点の集合はそんなに大きくありません。ただしクエリの個数が多いので訪問済みフラグを配列にするとその都度初期化の処理が必要になり TLE してしまいます。なので HashSet で管理します。

class Program
{
    static List<int> Bfs(List<int>[] G, int start, int k)
    {
        List<int> res = new List<int>();
        res.Add(start);

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

        q.Enqueue((start, 0));
        seen.Add(start);

        while (q.Count > 0)
        {
            var cur = q.Dequeue();
            int dist = cur.Item2;
            foreach (var next in G[cur.Item1])
            {
                if (seen.Contains(next))
                    continue;

                seen.Add(next);
                if (dist + 1 <= k)
                {
                    q.Enqueue((next, dist + 1));
                    res.Add(next);
                }
            }
        }
        return res;
    }

    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[] ab = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            int a = ab[0] - 1;
            int b = ab[1] - 1;
            G[a].Add(b);
            G[b].Add(a);
        }

        int Q = int.Parse(Console.ReadLine());
        List<long> ans = new List<long>();

        for (int i = 0; i < Q; i++)
        {
            int[] xk = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            int x = xk[0] - 1;
            int k = xk[1];
            List<int> res = Bfs(G, x, k);
            long ans0 = 0;
            foreach (var v in res)
                ans0 += v + 1;
            ans.Add(ans0);
        }
        foreach (long v in ans)
            Console.WriteLine(v);
    }
}

class Program

{

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

{

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

res.Add(start);

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

HashSet<int> seen = new HashSet<int>();

q.Enqueue((start, 0));

seen.Add(start);

while (q.Count > 0)

{

var cur = q.Dequeue();

int dist = cur.Item2;

foreach (var next in G[cur.Item1])

{

if (seen.Contains(next))

continue;

seen.Add(next);

if (dist + 1 <= k)

{

q.Enqueue((next, dist + 1));

res.Add(next);

}

return res;

}

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[] ab = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int a = ab[0] - 1;

int b = ab[1] - 1;

G[a].Add(b);

G[b].Add(a);

}

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

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

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

{

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

int x = xk[0] - 1;

int k = xk[1];

List<int> res = Bfs(G, x, k);

long ans0 = 0;

foreach (var v in res)

ans0 += v + 1;

ans.Add(ans0);

}

foreach (long v in ans)

Console.WriteLine(v);

}

D – Swapping Puzzle

問題の概要

H 行 W 列の 2 つのグリッド A, B が与えられる。
グリッド A のある行ととなりの行、またはある列ととなりの列を入れ替えることを繰り返すことで、グリッド A をグリッド B に一致させることが可能かどうかを判定せよ。
一致させることが可能な場合は操作回数の最小値も求めよ。

実際にグリッド A のある行ととなりの行、またはある列ととなりの列を入れ替える操作を繰り返した結果を求め、それを幅優先探索していけばよいです。

using System.Text;

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

        int[,] A = new int[H, W];
        for (int r = 0; r < H; r++)
        {
            int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            for (int c = 0; c < W; c++)
                A[r, c] = vs[c];
        }

        int[,] B = new int[H, W];
        for (int r = 0; r < H; r++)
        {
            int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            for (int c = 0; c < W; c++)
                B[r, c] = vs[c];
        }

        Queue<int[,]> q = new Queue<int[,]>();
        q.Enqueue(A);

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

        while (q.Count > 0)
        {
            int[,] cur = q.Dequeue();
            int dist = dic[GetKey(cur)];
            foreach (int[,] next in GetNexts(cur))
            {
                string n_key = GetKey(next);
                if (dic.ContainsKey(n_key))
                    continue;

                q.Enqueue(next);
                dic.Add(n_key, dist + 1);
            }
        }
        Console.WriteLine(dic.ContainsKey(GetKey(B)) ? dic[GetKey(B)] : -1);

        // グリッドを文字列に変換する
        string GetKey(int[,] grid)
        {
            StringBuilder sb = new StringBuilder();
            for (int r = 0; r < H; r++)
            {
                for (int c = 0; c < W; c++)
                {
                    sb.Append(grid[r, c]);
                    sb.Append(' ');
                }
            }
            return sb.ToString();
        }

        // となりの行、またはとなりの列と入れ替えたグリッドをすべて求める
        List<int[,]> GetNexts(int[,] grid)
        {
            List<int[,]> res = new List<int[,]>();
            for (int r = 0; r < H - 1; r++)
                res.Add(SwapRow(grid, r, r + 1));
            for (int c = 0; c < W - 1; c++)
                res.Add(SwapCol(grid, c, c + 1));
            return res;
        }

        // a 行と b 行を入れ替えたグリッドを求める
        int[,] SwapRow(int[,] grid, int a, int b)
        {
            int[,] res = (int[,])grid.Clone();
            for (global::System.Int32 i = 0; i < W; i++)
                (res[a, i], res[b, i]) = (res[b, i], res[a, i]);
            return res;
        }

        // a 列と b 列を入れ替えたグリッドを求める
        int[,] SwapCol(int[,] grid, int a, int b)
        {
            int[,] res = (int[,])grid.Clone();
            for (global::System.Int32 i = 0; i < H; i++)
                (res[i, a], res[i, b]) = (res[i, b], res[i, a]);
            return res;
        }
    }
}

using System.Text;

class Program

{

static void Main()

{

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

int H = hw[0];

int W = hw[1];

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

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

{

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

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

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

}

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

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

{

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

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

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

}

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

q.Enqueue(A);

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

dic.Add(GetKey(A), 0);

while (q.Count > 0)

{

int[,] cur = q.Dequeue();

int dist = dic[GetKey(cur)];

foreach (int[,] next in GetNexts(cur))

{

string n_key = GetKey(next);

if (dic.ContainsKey(n_key))

continue;

q.Enqueue(next);

dic.Add(n_key, dist + 1);

}

Console.WriteLine(dic.ContainsKey(GetKey(B)) ? dic[GetKey(B)] : -1);

// グリッドを文字列に変換する

string GetKey(int[,] grid)

{

StringBuilder sb = new StringBuilder();

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

{

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

{

sb.Append(grid[r, c]);

sb.Append(' ');

}

return sb.ToString();

}

// となりの行、またはとなりの列と入れ替えたグリッドをすべて求める

List<int[,]> GetNexts(int[,] grid)

{

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

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

res.Add(SwapRow(grid, r, r + 1));

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

res.Add(SwapCol(grid, c, c + 1));

return res;

}

// a 行と b 行を入れ替えたグリッドを求める

int[,] SwapRow(int[,] grid, int a, int b)

{

int[,] res = (int[,])grid.Clone();

for (global::System.Int32 i = 0; i < W; i++)

(res[a, i], res[b, i]) = (res[b, i], res[a, i]);

return res;

}

// a 列と b 列を入れ替えたグリッドを求める

int[,] SwapCol(int[,] grid, int a, int b)

{

int[,] res = (int[,])grid.Clone();

for (global::System.Int32 i = 0; i < H; i++)

(res[i, a], res[i, b]) = (res[i, b], res[i, a]);

return res;

}

E – Avoid Eye Contact

問題の概要

H 行 W 列のグリッド状に分割されたフィールドがあり、そこにはスタート地点とゴール地点、障害物と人が存在する。
障害物があるマスを通らず、そして人の視線に一度も入らずにゴール地点に到達できるか判定せよ。到達できる場合はそのために必要な移動回数の最小値を求めよ。

人がいるところとその視界を障害物に置き換えます。あとはグリッド上の幅優先探索をしてゴールまでの最短経路長を求めればよいです。

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 Main()
    {
        int[] hw = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
        int H = hw[0];
        int W = hw[1];

        char[,] A = new char[H, W];
        (int, int) start = (0, 0);
        (int, int) goal = (0, 0);
        List<(int, int)> U = new List<(int, int)>();
        List<(int, int)> D = new List<(int, int)>();
        List<(int, int)> L = new List<(int, int)>();
        List<(int, int)> R = new List<(int, int)>();
        List<(int, int)> N = new List<(int, int)>();
        for (int r = 0; r < H; r++)
        {
            char[] vs = Console.ReadLine().ToArray();
            for (int c = 0; c < W; c++)
            {
                A[r, c] = vs[c];

                if (vs[c] == 'S')
                    start = (r, c);
                if (vs[c] == 'G')
                    goal = (r, c);
                if (vs[c] == '<')
                    L.Add((r, c));
                if (vs[c] == '>')
                    R.Add((r, c));
                if (vs[c] == '^')
                    U.Add((r, c));
                if (vs[c] == 'v')
                    D.Add((r, c));
                if (vs[c] == '#')
                    N.Add((r, c));
            }
        }

        bool[,] grid = new bool[H, W];
        for (int r = 0; r < H; r++)
        {
            for (int c = 0; c < W; c++)
                grid[r, c] = true;
        }

        foreach (var tp in N)
        {
            grid[tp.Item1, tp.Item2] = false;
        }

        foreach (var tp in U)
        {
            int c = tp.Item2;
            grid[tp.Item1, c] = false;

            for (int r = tp.Item1 - 1; r >= 0; r--)
            {
                grid[r, c] = false;
                if (A[r, c] != '.' && A[r, c] != 'S' && A[r, c] != 'G')
                    break;
            }
        }
        foreach (var tp in D)
        {
            int c = tp.Item2;
            grid[tp.Item1, c] = false;

            for (int r = tp.Item1 + 1; r < H; r++)
            {
                grid[r, c] = false;
                if (A[r, c] != '.' && A[r, c] != 'S' && A[r, c] != 'G')
                    break;
            }
        }
        foreach (var tp in L)
        {
            int r = tp.Item1;
            grid[r, tp.Item2] = false;

            for (int c = tp.Item2 - 1; c >= 0; c--)
            {
                grid[r, c] = false;
                if (A[r, c] != '.' && A[r, c] != 'S' && A[r, c] != 'G')
                    break;
            }
        }
        foreach (var tp in R)
        {
            int r = tp.Item1;
            grid[r, tp.Item2] = false;
            for (int c = tp.Item2 + 1; c < W; c++)
            {
                grid[r, c] = false;
                if (A[r, c] != '.' && A[r, c] != 'S' && A[r, c] != 'G')
                    break;
            }
        }

        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, start.Item1, start.Item2, dists);
        Console.WriteLine(dists[goal.Item1, goal.Item2] < int.MaxValue ? dists[goal.Item1, goal.Item2] : -1);
    }
}

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

140

141

142

143

144

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 Main()

{

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

int H = hw[0];

int W = hw[1];

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

(int, int) start = (0, 0);

(int, int) goal = (0, 0);

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

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

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

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

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

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

{

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

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

{

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

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

start = (r, c);

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

goal = (r, c);

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

L.Add((r, c));

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

R.Add((r, c));

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

U.Add((r, c));

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

D.Add((r, c));

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

N.Add((r, c));

}

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

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

{

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

grid[r, c] = true;

}

foreach (var tp in N)

{

grid[tp.Item1, tp.Item2] = false;

}

foreach (var tp in U)

{

int c = tp.Item2;

grid[tp.Item1, c] = false;

for (int r = tp.Item1 - 1; r >= 0; r--)

{

grid[r, c] = false;

if (A[r, c] != '.' && A[r, c] != 'S' && A[r, c] != 'G')

break;

}

foreach (var tp in D)

{

int c = tp.Item2;

grid[tp.Item1, c] = false;

for (int r = tp.Item1 + 1; r < H; r++)

{

grid[r, c] = false;

if (A[r, c] != '.' && A[r, c] != 'S' && A[r, c] != 'G')

break;

}

foreach (var tp in L)

{

int r = tp.Item1;

grid[r, tp.Item2] = false;

for (int c = tp.Item2 - 1; c >= 0; c--)

{

grid[r, c] = false;

if (A[r, c] != '.' && A[r, c] != 'S' && A[r, c] != 'G')

break;

}

foreach (var tp in R)

{

int r = tp.Item1;

grid[r, tp.Item2] = false;

for (int c = tp.Item2 + 1; c < W; c++)

{

grid[r, c] = false;

if (A[r, c] != '.' && A[r, c] != 'S' && A[r, c] != 'G')

break;

}

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, start.Item1, start.Item2, dists);

Console.WriteLine(dists[goal.Item1, goal.Item2] < int.MaxValue ? dists[goal.Item1, goal.Item2] : -1);

}

D – Grid Ice Floor

問題の概要

N×M のグリッドがあり、すべてのマスは氷か岩のどちらかである。
この上にプレイヤーがいる。
プレイヤーは移動を開始したら岩のマスにぶつかるまでその方向に移動し続ける。
プレイヤーが通過または上で停止することができる氷の数を求めよ。

プレイヤーは移動を開始したら岩のマスにぶつかるまでその方向に移動し続けるという制約があるので、単純な幅優先探索ではなくプレイヤーの移動方向という情報も持たせて考えなければなりません。頂点倍化の幅優先探索です。

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

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

        (int, int)[] diffs = [(0, 1), (0, -1), (1, 0), (-1, 0)]; // R, L, D, U

        bool[,,] seen = new bool[4, N, M];
        seen[0, 1, 1] = true;
        seen[2, 1, 1] = true;

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

        while (q.Count > 0)
        {
            var cur = q.Dequeue();
            int z = cur.Item1;
            int r = cur.Item2;
            int c = cur.Item3;
            int dr = diffs[cur.Item1].Item1;
            int dc = diffs[cur.Item1].Item2;
            int nr = r + dr;
            int nc = c + dc;
            if(nr < 0 || nr >= N || nc < 0 || nc >= M)
                continue;

            if (seen[z, nr, nc])
                continue;

            if (grid[nr, nc] == '.') // 氷上を移動しているので方向転換することなく同じ方向に移動
            {
                seen[z, nr, nc] = true;
                q.Enqueue((z, nr, nc));
            }
            else // 岩にぶつかっているので移動可能な方向に方向転換する
            {
                for (int nz = 0; nz < 4; nz++)
                {
                    dr = diffs[nz].Item1;
                    dc = diffs[nz].Item2;
                    nr = r + dr;
                    nc = c + dc;
                    if (nr < 0 || nr >= N || nc < 0 || nc >= M)
                        continue;
                    if (seen[nz, nr, nc])
                        continue;
                    if (grid[nr, nc] == '.')
                    {
                        seen[nz, nr, nc] = true;
                        q.Enqueue((nz, nr, nc));
                    }
                }
            }
        }

        int ans = 0;
        for (int r = 0; r < N; r++)
        {
            for (int c = 0; c < M; c++)
            {
                bool ok = false;
                for (int z = 0; z < 4; z++)
                {
                    if (seen[z, r, c])
                        ok = true;
                }
                if (ok)
                    ans++;
            }
        }
        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];

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

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

{

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

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

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

}

(int, int)[] diffs = [(0, 1), (0, -1), (1, 0), (-1, 0)]; // R, L, D, U

bool[,,] seen = new bool[4, N, M];

seen[0, 1, 1] = true;

seen[2, 1, 1] = true;

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

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

q.Enqueue((2, 1, 1));

while (q.Count > 0)

{

var cur = q.Dequeue();

int z = cur.Item1;

int r = cur.Item2;

int c = cur.Item3;

int dr = diffs[cur.Item1].Item1;

int dc = diffs[cur.Item1].Item2;

int nr = r + dr;

int nc = c + dc;

if(nr < 0 || nr >= N || nc < 0 || nc >= M)

continue;

if (seen[z, nr, nc])

continue;

if (grid[nr, nc] == '.') // 氷上を移動しているので方向転換することなく同じ方向に移動

{

seen[z, nr, nc] = true;

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

}

else // 岩にぶつかっているので移動可能な方向に方向転換する

{

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

{

dr = diffs[nz].Item1;

dc = diffs[nz].Item2;

nr = r + dr;

nc = c + dc;

if (nr < 0 || nr >= N || nc < 0 || nc >= M)

continue;

if (seen[nz, nr, nc])

continue;

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

{

seen[nz, nr, nc] = true;

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

}

int ans = 0;

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

{

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

{

bool ok = false;

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

{

if (seen[z, r, c])

ok = true;

}

if (ok)

ans++;

}

Console.WriteLine(ans);

}

E – Hopscotch Addict

問題の概要

N 頂点 M 辺の単純有向グラフがある。
「『自分の今いる頂点から出ている辺を 1 つ選んで、その辺が接続する頂点に移動する』という操作をちょうど 3 回連続で行なう」を 1 セットとしたとき、頂点 S から頂点 T まで移動することは可能だろうか？移動可能である場合はセットの最小値も求めよ。

1 セットが 3 回連続の移動なのでその移動は3回中の何回目かがわかるようにして幅優先探索をします。これも頂点倍化の幅優先探索です。

class Program
{
    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);
        }

        int[] st = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
        int S = st[0] - 1;
        int T = st[1] - 1;

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

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

        while (q.Count > 0)
        {
            var tp = q.Dequeue();
            int v = tp.Item1;
            int cnt = tp.Item2;
            int dist = dists[v, cnt];

            foreach (int next in G[v])
            {
                if (dists[next, (cnt + 1) % 3] > dist + 1)
                {
                    dists[next, (cnt + 1) % 3] = dist + 1;
                    q.Enqueue((next, (cnt + 1) % 3));
                }
            }
        }
        Console.WriteLine(dists[T, 0] < int.MaxValue ? dists[T, 0] / 3 : -1);
    }
}

class Program

{

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);

}

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

int S = st[0] - 1;

int T = st[1] - 1;

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

q.Enqueue((S, 0));

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

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

{

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

dists[a, b] = int.MaxValue;

}

dists[S, 0] = 0;

while (q.Count > 0)

{

var tp = q.Dequeue();

int v = tp.Item1;

int cnt = tp.Item2;

int dist = dists[v, cnt];

foreach (int next in G[v])

{

if (dists[next, (cnt + 1) % 3] > dist + 1)

{

dists[next, (cnt + 1) % 3] = dist + 1;

q.Enqueue((next, (cnt + 1) % 3));

}

Console.WriteLine(dists[T, 0] < int.MaxValue ? dists[T, 0] / 3 : -1);

}

D – Teleport Maze

問題の概要

H 行 W 列のマス目からなる迷路が与えられる。
. : 空きマス
# : 障害物マス
英小文字（a – z）: ワープマス
マス (1, 1) からマス (H, W) へ移動することが可能かどうか判定し、可能ならばそれに必要な最小の合計行動回数を求めよ。

移動が可能なマス同士をつないで幅優先探索で最短経路長を求めるのですが、ワープマスをすべて直接つなごうとすると辺の数が厖大になります。そこで超頂点を導入します。グリッドとは別に 26 個の超頂点を用意し、’a’ であれば ‘a’ の超頂点と ‘a’ のマスを結びます。これだと辺の数を減らすことができるので TLE を回避することができます。

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

        int CharToInt(char ch) => ch - 'a';

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

        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 i = CharToInt(vs[c]);
                if (0 <= i && i <= 26)
                    warps[i].Add((r, c));
            }
        }

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

        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[0, 0] = 0;

        int[] dists2 = new int[26];
        Array.Fill(dists2, int.MaxValue);

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

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

            if (r == -1)
            {
                foreach (var pos in warps[c])
                {
                    if (dists[pos.Item1, pos.Item2] > dist)
                    {
                        dists[pos.Item1, pos.Item2] = dist;
                        q.Enqueue((pos.Item1, pos.Item2));
                    }
                }
                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 (grid[nr, nc] == '#')
                    continue;

                if (dists[nr, nc] > dist + 1)
                {
                    dists[nr, nc] = dist + 1;
                    q.Enqueue((nr, nc));
                }
            }
            if ('a' <= grid[r, c] && grid[r, c] <= 'z' && dists2[CharToInt(grid[r, c])] > dist + 1)
            {
                dists2[CharToInt(grid[r, c])] = dist + 1;
                q.Enqueue((-1, CharToInt(grid[r, c])));
            }
        }
        Console.WriteLine(dists[H - 1, W - 1] < int.MaxValue ? dists[H - 1, W - 1] : -1);
    }
}

class Program

{

static void Main()

{

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

int H = hw[0];

int W = hw[1];

int CharToInt(char ch) => ch - 'a';

List<(int, int)>[] warps = new List<(int, int)>[26];

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

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

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 i = CharToInt(vs[c]);

if (0 <= i && i <= 26)

warps[i].Add((r, c));

}

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

q.Enqueue((0, 0));

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[0, 0] = 0;

int[] dists2 = new int[26];

Array.Fill(dists2, int.MaxValue);

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

while (q.Count > 0)

{

var cur = q.Dequeue();

int r = cur.Item1;

int c = cur.Item2;

int dist = r >= 0 ? dists[r, c] : dists2[c];

if (r == -1)

{

foreach (var pos in warps[c])

{

if (dists[pos.Item1, pos.Item2] > dist)

{

dists[pos.Item1, pos.Item2] = dist;

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

}

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 (grid[nr, nc] == '#')

continue;

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

{

dists[nr, nc] = dist + 1;

q.Enqueue((nr, nc));

}

if ('a' <= grid[r, c] && grid[r, c] <= 'z' && dists2[CharToInt(grid[r, c])] > dist + 1)

{

dists2[CharToInt(grid[r, c])] = dist + 1;

q.Enqueue((-1, CharToInt(grid[r, c])));

}

Console.WriteLine(dists[H - 1, W - 1] < int.MaxValue ? dists[H - 1, W - 1] : -1);

}

D – People on a Line

問題の概要

x 軸上に N 人の人が立っている。人 i の位置は X[i] である。
X[R[i]] – X[L[i]] = D[i] という情報が M 個与えられる。
矛盾しない数列 X が存在するかどうか判定せよ。

ポテンシャル付き Union-Findでも解くことができるが幅優先探索でも解けます。

情報がある頂点間に重みを持つ有向辺を張ります。逆方向であれば重みの符号を反転させます。探索開始点となる頂点の X の値を 0 とし、辺でつながっている頂点に値を設定していきます。構築された有向グラフは連結とは限らないので幅優先探索が完了したら値が設定されていない頂点を探してそこからの幅優先探索を繰り返します。

途中で設定されている値と矛盾があれば”No”が答えです。そうでないなら”Yes”が答えです。

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[] lrd = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            int l = lrd[0] - 1;
            int r = lrd[1] - 1;
            int d = lrd[2];
            G[l].Add((r, d));
            G[r].Add((l, -d));
        }

        long[] dists = new long[N];
        Array.Fill(dists, long.MaxValue);

        bool yes = true;
        for (int i = 0; i < N; i++)
        {
            if (dists[i] == long.MaxValue)
                yes &= CheckByBfs(i);
        }
        Console.WriteLine(yes ? "Yes" : "No");

        bool CheckByBfs(int start)
        {
            Queue<int> q = new Queue<int>();
            q.Enqueue(start);
            dists[start] = 0;

            while (q.Count > 0)
            {
                var cur = q.Dequeue();
                var dist = dists[cur];
                foreach (var edge in G[cur])
                {
                    if (dists[edge.Item1] == long.MaxValue)
                    {
                        dists[edge.Item1] = dist + edge.Item2;
                        q.Enqueue(edge.Item1);
                    }
                    else if (dists[edge.Item1] != dist + edge.Item2)
                        return false;
                }
            }
            return true;
        }
    }
}

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[] lrd = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int l = lrd[0] - 1;

int r = lrd[1] - 1;

int d = lrd[2];

G[l].Add((r, d));

G[r].Add((l, -d));

}

long[] dists = new long[N];

Array.Fill(dists, long.MaxValue);

bool yes = true;

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

{

if (dists[i] == long.MaxValue)

yes &= CheckByBfs(i);

}

Console.WriteLine(yes ? "Yes" : "No");

bool CheckByBfs(int start)

{

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

q.Enqueue(start);

dists[start] = 0;

while (q.Count > 0)

{

var cur = q.Dequeue();

var dist = dists[cur];

foreach (var edge in G[cur])

{

if (dists[edge.Item1] == long.MaxValue)

{

dists[edge.Item1] = dist + edge.Item2;

q.Enqueue(edge.Item1);

}

else if (dists[edge.Item1] != dist + edge.Item2)

return false;

}

return true;

}

D – うほょじご

問題の概要

正の整数 N, M が与えられる。
1 ≦ x ≦ N, 1 ≦ y ≦ M なる整数の組 (x, y) であって、以下の一連の操作を無限に繰り返すことができるものの個数を求めよ。
（操作）
x, y のいずれかが 0 なら、終了する。
x < y なら x を rev(x) で、そうでないなら y を rev(y) で置き換える。
上の操作後、x < y となっていれば y を y – x で、そうでなければ x を x – y で置き換える。
rev(x)：x を 10 進表記してできる文字列を反転したもの

1 ≦ x ≦ N, 1 ≦ y ≦ M なるすべての整数の組 (x, y) が (0, ?) または (?, 0) になるか調べていると時間がかかります。問題の制約から操作を繰り返しても 1 ≦ x, y ≦ 999 であることに着目します。

まず 1000 × 1000 個の頂点を用意します。そして操作によって (x1, y1) が (x2, y2) に変化するのであれば頂点 (1000 * x2 + y2) から頂点 (1000 * x1 + y1) へ辺を張ります（辺を逆向きにするのがポイント）。そして頂点 (1000 * ?) と頂点 ? から多始点幅優先探索をおこないます。到達できた頂点のなかから 1 ≦ x ≦ N, 1 ≦ y ≦ M である整数の組 (x, y) に相当する頂点の数を数えればよいです。

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

        (int, int) GetNext(int x, int y)
        {
            if (x == 0 || y == 0)
                return (0, 0);

            if (x < y)
                x = int.Parse(new string(x.ToString().Reverse().ToArray()));
            else
                y = int.Parse(new string(y.ToString().Reverse().ToArray()));

            if (x < y)
                y -= x;
            else
                x -= y;

            return (x, y);
        }

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

        for (int x = 0; x < 1000; x++)
        {
            for (int y = 0; y < 1000; y++)
            {
                var res = GetNext(x, y);

                // (1000 * x + y) -> (1000 * res.Item1 + res.Item2) に遷移するので
                // これとは逆向きの辺を張る
                G[1000 * res.Item1 + res.Item2].Add(1000 * x + y);
            }
        }

        Queue<int> q = new Queue<int>();
        bool[] seen = new bool[1000 * 1000];

        for (int i = 0; i < 1000; i++)
        {
            q.Enqueue(i);
            q.Enqueue(1000 * i);
            seen[i] = true;
            seen[1000 * i] = true;
        }

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

                seen[next] = true;
                q.Enqueue(next);
            }
        }

        int ans = 0;
        for (int x = 0; x <= N; x++)
        {
            for (int y = 0; y <= M; y++)
            {
                if (!seen[1000 * x + y])
                    ans++;
            }
        }
        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];

(int, int) GetNext(int x, int y)

{

if (x == 0 || y == 0)

return (0, 0);

if (x < y)

x = int.Parse(new string(x.ToString().Reverse().ToArray()));

else

y = int.Parse(new string(y.ToString().Reverse().ToArray()));

if (x < y)

y -= x;

else

x -= y;

return (x, y);

}

List<int>[] G = new List<int>[1000 * 1000];

for (int i = 0; i < 1000 * 1000; i++)

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

for (int x = 0; x < 1000; x++)

{

for (int y = 0; y < 1000; y++)

{

var res = GetNext(x, y);

// (1000 * x + y) -> (1000 * res.Item1 + res.Item2) に遷移するので

// これとは逆向きの辺を張る

G[1000 * res.Item1 + res.Item2].Add(1000 * x + y);

}

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

bool[] seen = new bool[1000 * 1000];

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

{

q.Enqueue(i);

q.Enqueue(1000 * i);

seen[i] = true;

seen[1000 * i] = true;

}

while (q.Count > 0)

{

int cur = q.Dequeue();

foreach (int next in G[cur])

{

if (seen[next])

continue;

seen[next] = true;

q.Enqueue(next);

}

int ans = 0;

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

{

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

{

if (!seen[1000 * x + y])

ans++;

}

Console.WriteLine(ans);

}

A70 – Lanterns

問題の概要

N 個のランプが机の上に置かれている。
操作 i をおこなうとランプ X[i], Y[i], Z[i] の状態を同時に反転させることができる。
すべてのランプの状態を ON にすることができるか判定せよ。
できる場合は操作の最小回数も求めよ。

問題の制約では N ≦ 10 なのでランプがとりうる状態は最大でも 1024 個です。なので幅優先探索をすれば解を得ることができます。

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

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

        int start = 0;
        for (int i = 0; i < N; i++)
        {
            if (A[i] == 1)
                start |= (1 << i);
        }

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

        for (int i = 0; i < M; i++)
        {
            int[] xyz = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            int x = xyz[0] - 1;
            int y = xyz[1] - 1;
            int z = xyz[2] - 1;
            for (int bit = 0; bit < 1 << N; bit++)
            {
                int v = bit;
                v ^= 1 << x;
                v ^= 1 << y;
                v ^= 1 << z;
                G[bit].Add(v);
            }
        }

        Queue<int> q = new Queue<int>();
        int[] dists = new int[1 << N];
        Array.Fill(dists, int.MaxValue);

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

        while (q.Count > 0)
        {
            int cur = q.Dequeue();
            int dist = dists[cur];
            foreach (int next in G[cur])
            {
                if (dists[next] > dist + 1)
                {
                    dists[next] = dist + 1;
                    q.Enqueue(next);
                }
            }
        }
        int ans = dists[(1 << N) - 1];
        Console.WriteLine(ans < int.MaxValue ? ans : -1);
    }
}

class Program

{

static void Main()

{

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

int N = nm[0];

int M = nm[1];

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

int start = 0;

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

{

if (A[i] == 1)

start |= (1 << i);

}

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

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

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

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

{

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

int x = xyz[0] - 1;

int y = xyz[1] - 1;

int z = xyz[2] - 1;

for (int bit = 0; bit < 1 << N; bit++)

{

int v = bit;

v ^= 1 << x;

v ^= 1 << y;

v ^= 1 << z;

G[bit].Add(v);

}

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

int[] dists = new int[1 << N];

Array.Fill(dists, int.MaxValue);

q.Enqueue(start);

dists[start] = 0;

while (q.Count > 0)

{

int cur = q.Dequeue();

int dist = dists[cur];

foreach (int next in G[cur])

{

if (dists[next] > dist + 1)

{

dists[next] = dist + 1;

q.Enqueue(next);

}

int ans = dists[(1 << N) - 1];

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

}

B – パンケーキ (Pancake)

問題の概要

‘A’,’B’,’C’のみからなる N 文字の文字列が Q 回与えられる。
それぞれについて先頭から k 文字だけ反転させる操作を繰り返すことで文字列が昇順ソートされた状態に変更したい。必要な反転操作の回数の最小値を求めよ。

すべての’A’,’B’,’C’のみからなる N 文字の文字列を対象に多始点幅優先探索すればよいです。処理を高速化するために文字列を数値に変換します（文字列を三進数と考えればよい）。すべての文字列から昇順ソートされた文字列への最短経路長を計算しようとすると時間がかかるので、遷移を逆にして昇順ソートされた文字列からそれ以外の文字列への最短経路長を求めます。この前処理があれば Q 回のクエリに対して O(1) で解を返すことができるようになります。

class Program
{
    static void Main()
    {
        // 文字列から整数値へ
        int encode(string S)
        {
            int res = 0;
            foreach (char ch in S)
                res = res * 3 + (ch - 'A');
            return res;
        }

        // 整数値から文字列へ
        string decode(int N, int val)
        {
            List<char> res = new List<char>();
            while (val > 0)
            {
                res.Add((char)('A' + (val % 3)));
                val /= 3;
            }
            while (res.Count < N)
                res.Add('A');
            res.Reverse();
            return new string(res.ToArray());
        }

        int[] nq = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
        int N = nq[0];
        int Q = nq[1];

        int v_cnt = (int)Math.Pow(3, N);

        Queue<int> q = new Queue<int>();
        int[] dists = new int[v_cnt];
        Array.Fill(dists, int.MaxValue);

        for (int a = 0; a <= N; a++)
        {
            for (int b = 0; b <= N - a; b++)
            {
                System.Text.StringBuilder sb = new System.Text.StringBuilder();
                sb.Append('A', a);
                sb.Append('B', b);
                sb.Append('C', N - a - b);
                int val = encode(sb.ToString());
                q.Enqueue(val);
                dists[val] = 0;
            }
        }

        while (q.Count > 0)
        {
            var cur = q.Dequeue();

            List<char> s = decode(N, cur).ToList();

            for (int i = 2; i <= N; i++)
            {
                s.Reverse(0, i);
                int nv = encode(new string(s.ToArray()));
                s.Reverse(0, i);

                if (dists[nv] > dists[cur] + 1)
                {
                    dists[nv] = dists[cur] + 1;
                    q.Enqueue(nv);
                }
            }
        }

        List<int> ans = new List<int>();
        for (int i = 0; i < Q; i++)
            ans.Add(dists[encode(Console.ReadLine())]);

        foreach (var v in ans)
            Console.WriteLine(v);
    }
}

class Program

{

static void Main()

{

// 文字列から整数値へ

int encode(string S)

{

int res = 0;

foreach (char ch in S)

res = res * 3 + (ch - 'A');

return res;

}

// 整数値から文字列へ

string decode(int N, int val)

{

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

while (val > 0)

{

res.Add((char)('A' + (val % 3)));

val /= 3;

}

while (res.Count < N)

res.Add('A');

res.Reverse();

return new string(res.ToArray());

}

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

int N = nq[0];

int Q = nq[1];

int v_cnt = (int)Math.Pow(3, N);

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

int[] dists = new int[v_cnt];

Array.Fill(dists, int.MaxValue);

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

{

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

{

System.Text.StringBuilder sb = new System.Text.StringBuilder();

sb.Append('A', a);

sb.Append('B', b);

sb.Append('C', N - a - b);

int val = encode(sb.ToString());

q.Enqueue(val);

dists[val] = 0;

}

while (q.Count > 0)

{

var cur = q.Dequeue();

List<char> s = decode(N, cur).ToList();

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

{

s.Reverse(0, i);

int nv = encode(new string(s.ToArray()));

s.Reverse(0, i);

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

{

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

q.Enqueue(nv);

}

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

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

ans.Add(dists[encode(Console.ReadLine())]);

foreach (var v in ans)

Console.WriteLine(v);

}

D – テンキー (Tenkey)

問題の概要

テンキーがあり、現在選択されている位置は 0 である。
操作 1 と 2 を繰り返すことで入力された値が M で割った余りが R であるようにしたい。操作回数の最小値を求めよ。
操作 1：テンキーの現在選択されている位置を隣に変更する。
操作 2：キーを押下する。この場合はすでに入力されていた数字のすぐ右に新たな数字が入力される。

入力されている値と現在選択されているキーで幅優先探索をすればよいです。新しい数字を追加入力する処理は前の値を 10 倍して M の剰余をとればよいです。

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

        int[][] next_keys = new int[10][];
        next_keys[0] = [1];
        next_keys[1] = [0, 2, 4];
        next_keys[2] = [1, 3, 5];
        next_keys[3] = [2, 6];
        next_keys[4] = [1, 5, 7];
        next_keys[5] = [2, 4, 6, 8];
        next_keys[6] = [3, 5, 9];
        next_keys[7] = [4, 8];
        next_keys[8] = [5, 7, 9];
        next_keys[9] = [6, 8];

        List<(int num, int key)> GetNexts((int num, int key) cur)
        {
            List<(int num, int key)> res = new List<(int num, int key)>();
            foreach (int next_key in next_keys[cur.key])
                res.Add((cur.num, next_key));

            res.Add(((cur.num * 10 + cur.key) % M, cur.key));
            return res;
        }

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

        int[,] dists = new int[M, 10];
        for (int a = 0; a < M; a++)
        {
            for (int b = 0; b < 10; b++)
                dists[a, b] = int.MaxValue;
        }

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

        bool find = false;
        while (q.Count > 0)
        {
            var cur = q.Dequeue();
            var nexts = GetNexts(cur);
            int cnt = dists[cur.num, cur.key];

            foreach (var next in nexts)
            {
                if (dists[next.num, next.key] > cnt + 1)
                {
                    dists[next.num, next.key] = cnt + 1;
                    q.Enqueue(next);
                    if (next.num == R)
                    {
                        find = true;
                        break;
                    }
                }
            }
            if (find)
                break;
        }

        int ans = int.MaxValue;
        for (int i = 0; i < 10; i++)
            ans = Math.Min(ans, dists[R, i]);
        Console.WriteLine(ans);
    }
}

class Program

{

static void Main()

{

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

int M = mr[0];

int R = mr[1];

int[][] next_keys = new int[10][];

next_keys[0] = [1];

next_keys[1] = [0, 2, 4];

next_keys[2] = [1, 3, 5];

next_keys[3] = [2, 6];

next_keys[4] = [1, 5, 7];

next_keys[5] = [2, 4, 6, 8];

next_keys[6] = [3, 5, 9];

next_keys[7] = [4, 8];

next_keys[8] = [5, 7, 9];

next_keys[9] = [6, 8];

List<(int num, int key)> GetNexts((int num, int key) cur)

{

List<(int num, int key)> res = new List<(int num, int key)>();

foreach (int next_key in next_keys[cur.key])

res.Add((cur.num, next_key));

res.Add(((cur.num * 10 + cur.key) % M, cur.key));

return res;

}

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

int[,] dists = new int[M, 10];

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

{

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

dists[a, b] = int.MaxValue;

}

dists[0, 0] = 0;

q.Enqueue((0, 0));

bool find = false;

while (q.Count > 0)

{

var cur = q.Dequeue();

var nexts = GetNexts(cur);

int cnt = dists[cur.num, cur.key];

foreach (var next in nexts)

{

if (dists[next.num, next.key] > cnt + 1)

{

dists[next.num, next.key] = cnt + 1;

q.Enqueue(next);

if (next.num == R)

{

find = true;

break;

}

if (find)

break;

}

int ans = int.MaxValue;

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

ans = Math.Min(ans, dists[R, i]);

Console.WriteLine(ans);

}

K – ガソリンスタンド

問題の概要

N 個の街と M 本の道路があり、道路は街 U[i] と V[i] を双方向に結んでいる。
K 個の街にはガソリンスタンドがある。
Q 個のクエリに答えよ。
クエリ：街 S[i] を出発し、ガソリンスタンドのある街を 1 つ以上通った後、街 T[i] に行くとき、道を通る回数の最小値を求めよ。

最初にガソリンスタンドから各街への最短経路長を求めておきます。
（ガソリンスタンド i から街 S[i] までの最短経路長 + ガソリンスタンド i から街 T[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];
        int Q = nm[2];
        int K = nm[3];

        int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
        A = A.Select(_ => _ - 1).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);
        }

        int[] S = new int[Q];
        int[] T = new int[Q];
        for (int i = 0; i < Q; i++)
        {
            int[] st = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            S[i] = st[0] - 1;
            T[i] = st[1] - 1;
        }

        List<int[]> distsList = new List<int[]>();
        for (int i = 0; i < A.Length; i++)
        {
            int[] dists = new int[N];
            Array.Fill(dists, int.MaxValue);
            Bfs(G, A[i], dists);
            distsList.Add(dists);
        }

        for (int i = 0; i < Q; i++)
        {
            int s = S[i];
            int t = T[i];

            int ans = int.MaxValue;
            foreach (int[] dists in distsList)
                ans = Math.Min(ans, dists[s] + dists[t]);

            Console.WriteLine(ans);
        }
    }
}

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];

int Q = nm[2];

int K = nm[3];

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

A = A.Select(_ => _ - 1).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);

}

int[] S = new int[Q];

int[] T = new int[Q];

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

{

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

S[i] = st[0] - 1;

T[i] = st[1] - 1;

}

List<int[]> distsList = new List<int[]>();

for (int i = 0; i < A.Length; i++)

{

int[] dists = new int[N];

Array.Fill(dists, int.MaxValue);

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

distsList.Add(dists);

}

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

{

int s = S[i];

int t = T[i];

int ans = int.MaxValue;

foreach (int[] dists in distsList)

ans = Math.Min(ans, dists[s] + dists[t]);

Console.WriteLine(ans);

}

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

E – Transitivity

E – Small d and k

D – Swapping Puzzle

E – Avoid Eye Contact

D – Grid Ice Floor

E – Hopscotch Addict

D – Teleport Maze

D – People on a Line

D – うほょじご

A70 – Lanterns

B – パンケーキ (Pancake)

D – テンキー (Tenkey)

K – ガソリンスタンド

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

コメントについて

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

コメントをどうぞ