AtCoder NoviStepsを埋めてみる(25) 幅優先探索 3Q 基本問題の続きです。今回も幅優先探索（BFS）です。
C – Tour
問題の概要
N 個の頂点とM 個の辺からなる有向グラフが与えられる。
始点と終点の組として考えられるものは何通りあるか求めよ。
N 個の頂点すべてについて、それぞれからたどり着ける頂点を数を数えればよいです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
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[] ab = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int a = ab[0] - 1; int b = ab[1] - 1; G[a].Add(b); } int ans = 0; for (int i = 0; i < N; i++) { int[] dists = new int[N]; Array.Fill(dists, int.MaxValue); Bfs(G, i, dists); ans += dists.Count(_ => _ < int.MaxValue); } Console.WriteLine(ans); } } |
C – Humidifier 3
問題の概要
H 行 W 列のマス目がある。
‘H’を始点とし、’#’を通らず上下左右に D 回以下の移動で辿り着けるマスの総数を求めよ。
‘H’は複数個ある場合があるので注意。
多始点型の幅優先探索です。Queue に始点となる頂点をすべて格納しておき、あとは普通の幅優先探索と同じ処理をおこないます。
他の問題でも使えそうなのでGridBfsメソッドを定義しておきます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
class Program { // グリッド上の多始点型の幅優先探索をおこなう。dists は int.MaxValue で初期化しておくこと。 static void GridBfs(bool[,] grid, int[,] dists, List<(int r, int c)> starts) { int h = grid.GetLength(0); int w = grid.GetLength(1); Queue<int> qR = new Queue<int>(); Queue<int> qC = new Queue<int>(); foreach (var start in starts) { qR.Enqueue(start.r); qC.Enqueue(start.c); dists[start.r, start.c] = 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[] hwd = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int H = hwd[0]; int W = hwd[1]; int D = hwd[2]; bool[,] grid = new bool[H, W]; int[,] dists = new int[H, W]; List<(int r, int c)> starts = new List<(int r, int c)>(); for (int r = 0; r < H; r++) { char[] vs = Console.ReadLine().ToArray(); for (int c = 0; c < W; c++) { dists[r, c] = int.MaxValue; grid[r, c] = vs[c] != '#'; if(vs[c] == 'H') starts.Add((r, c)); } } GridBfs(grid, dists, starts); int ans = 0; for (int r = 0; r < H; r++) { for (int c = 0; c < W; c++) { if (dists[r, c] <= D) ans++; } } Console.WriteLine(ans); } } |
A – Darker and Darker
縦 H 行、横 W 列の白黒に塗られたマス目が与えられる。
「黒色のマスの上下左右にある白マスを黒に塗り替える」という操作を繰り返してすべてのマスを黒くするには何回の操作が必要だろうか？
黒マスを始点に多始点型幅優先探索をおこない、黒マスからすべてのマスへの最短経路長を求めます。最短経路長の最大値が求めるべき解です。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
class Program { // Bfsメソッドは上記定義のとおり 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[,] dists = new int[H, W]; List<(int r, int c)> starts = new List<(int r, int c)>(); for (int r = 0; r < H; r++) { char[] vs = Console.ReadLine().ToArray(); for (int c = 0; c < W; c++) { dists[r, c] = int.MaxValue; grid[r, c] = true; if(vs[c] == '#') starts.Add((r, c)); } } GridBfs(grid, dists, starts); int ans = 0; for (int r = 0; r < H; r++) { for (int c = 0; c < W; c++) ans = Math.Max(ans, dists[r, c]); } Console.WriteLine(ans); } } |
D – “redocta”.swap(i,i+1)
問題の概要
atcoder の並べ替えである文字列 S が与えられる。
S 中の隣接する 2 文字を選び、入れ替える。
S を atcoder にするために必要な最小の操作回数は？
現在の文字列から「隣接する 2 文字を選び入れ替える」ことで得られる文字列をすべて取得して幅優先探索をおこなえば解が得られます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
class Program { static void Main() { string S = Console.ReadLine(); List<string> GetSwapStrings(string s) { List<string> res = new List<string>(); char[] chars = s.ToArray(); for (int i = 0; i < s.Length - 1; i++) { (chars[i], chars[i + 1]) = (chars[i + 1], chars[i]); res.Add(new string(chars)); (chars[i], chars[i + 1]) = (chars[i + 1], chars[i]); } return res; } Queue<string> q = new Queue<string>(); Dictionary<string, int> dic = new Dictionary<string, int>(); q.Enqueue(S); dic.Add(S, 0); while (q.Count > 0) { string s = q.Dequeue(); int v = dic[s]; List<string> nexts = GetSwapStrings(s); foreach (string next in nexts) { if (dic.ContainsKey(next)) continue; dic.Add(next, v + 1); q.Enqueue(next); } } Console.WriteLine(dic["atcoder"]); } } |
別解
転倒数を使ったほうが実は速いです。
転倒数とは左から順番に「自分より左にいるのに自分より大きい数」の個数を加算して得られる総和です。これはソートされた状態にするために何回隣の要素との入れ替えが必要になるかの回数と一致しています。
‘a’ = 0, ‘t’ = 1, ‘c’ = 2, … と値を割り当て S で int型配列をつくります。そして隣の要素を入れ替える操作を何回繰り返せばソートされた配列になるかを考えます。
長い数列の場合は転倒数を求めるにはセグメント木やFenwick木を用いる必要がありますが、この問題は文字列が短いので愚直なやり方で充分間に合います。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
class Program { static void Main() { string S = Console.ReadLine(); string T = "atcoder"; Dictionary<char, int> dic = new Dictionary<char, int>(); for (int i = 0; i < T.Length; i++) dic.Add(T[i], i); List<int> A = new List<int>(); foreach (char ch in S) A.Add(dic[ch]); int ans = 0; for (int i = 0; i < A.Count; i++) { for (int j = i + 1; j < A.Count; j++) { if (A[i] > A[j]) ans++; } } Console.WriteLine(ans); } } |
D – Multiply and Rotate
1 を a 倍するか 1 の位の数字を最上位の桁に移動させる操作を繰り返す場合、X にするために必要な操作の回数の最小値を求めよ。
1 を始点に幅優先探索をすればよいです。a 倍することで X の桁数を超えてしまう場合は考えなくてよいので操作によって得られる値の種類は最大で 10^6 通りしかありません。充分間に合います。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
class Program { static void Main() { int[] an = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int a = an[0]; int N = an[1]; int nlength = N.ToString().Length; List<int> GetNextNumbers(int v) { List<int> res = new List<int>(); long va = 1L * v * a; if (va.ToString().Length <= nlength) res.Add(v * a); if (v >= 10 && v % 10 != 0) { List<char> vs = v.ToString().ToList(); char last = vs.Last(); vs.RemoveAt(vs.Count - 1); vs.Insert(0, last); string s = new string(vs.ToArray()); res.Add(int.Parse(s)); } return res; } Queue<int> q = new Queue<int>(); Dictionary<int, int> dic = new Dictionary<int, int>(); q.Enqueue(1); dic.Add(1, 0); while (q.Count > 0) { int v = q.Dequeue(); int cnt = dic[v]; List<int> nexts = GetNextNumbers(v); foreach (int next in nexts) { if (dic.ContainsKey(next)) continue; q.Enqueue(next); dic.Add(next, cnt + 1); } } Console.WriteLine(dic.ContainsKey(N) ? dic[N] : -1); } } |
D – Maze Master
問題の概要
縦 H マス、横 W マスの H × W マスからなる迷路が与えられる。
始点と終点を適切に決めたとき、終点までの最短経路長の最大値を求めよ。
壁ではないすべてのマスを始点として各マスへの最短経路長を求めます。それらのなかから最大のものを選べばそれが解となります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
class Program { // GridBfsメソッドは上記定義のとおり 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]; for (int r = 0; r < H; r++) { char[] vs = Console.ReadLine().ToArray(); for (int c = 0; c < W; c++) grid[r, c] = vs[c] == '.'; } // 2次元配列をすべて int.MaxValue で初期化する int[,] InitDists() { 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; } return dists; } // 2次元配列内から int.MaxValue 以外の最大値を取得する int GetMax(int[,] dists) { int res = 0; for (int r = 0; r < H; r++) { for (int c = 0; c < W; c++) { if(dists[r, c] < int.MaxValue) res = Math.Max(res, dists[r, c]); } } return res; } int ans = 0; for (int r = 0; r < H; r++) { for (int c = 0; c < W; c++) { if (grid[r, c]) { List<(int r, int c)> starts = new List<(int r, int c)>(); starts.Add((r, c)); int[,] dists = InitDists(); GridBfs(grid, dists, starts); ans = Math.Max(ans, GetMax(dists)); } } } Console.WriteLine(ans); } } |
D – Toggle Maze
問題の概要
H 行 W 列のグリッドがある。
グリッド上には障害物だけでなくドアとスイッチがある。
スイッチがあるマスに移動することでドアの開閉状態が入れ替わる。
スタートマスからゴールマスへの最短経路長を求めよ。
スイッチがあるマスに移動することでドアの開閉状態が入れ替わるので、入れ替わる前と入れ替わった後の状態を示すグリッドを 2 つ用意します（スイッチを 2 回動作させると元の状態に戻るので 2 つあれば充分）。
現在位置がスイッチがあるマスである場合はドアの開閉状態が入れ替わったので現在見ているグリッドを切り替えます。やや複雑な幅優先探索の問題です。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 |
class Program { static void Main() { int[] hw = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int H = hw[0]; int W = hw[1]; int sr = 0; int sc = 0; int gr = 0; int gc = 0; char[,] grid0 = new char[H, W]; char[,] grid1 = new char[H, W]; for (int r = 0; r < H; r++) { char[] vs = Console.ReadLine().ToArray(); for (int c = 0; c < W; c++) { if (vs[c] == 'S') { sr = r; sc = c; } if (vs[c] == 'G') { gr = r; gc = c; } grid0[r, c] = vs[c]; grid1[r, c] = vs[c]; if (vs[c] == 'o') { grid0[r, c] = '.'; grid1[r, c] = '#'; } if (vs[c] == 'x') { grid0[r, c] = '#'; grid1[r, c] = '.'; } } } Queue<int> qR = new Queue<int>(); Queue<int> qC = new Queue<int>(); Queue<int> qZ = new Queue<int>(); int[,,] dists = new int[H, W, 2]; for (int r = 0; r < H; r++) { for (int c = 0; c < W; c++) { for (int d = 0; d < 2; d++) dists[r, c, d] = int.MaxValue; } } qR.Enqueue(sr); qC.Enqueue(sc); qZ.Enqueue(0); dists[sr, sc, 0] = 0; (int, int)[] diffs = [(0, 1), (0, -1), (1, 0), (-1, 0)]; while (qR.Count > 0) { int r = qR.Dequeue(); int c = qC.Dequeue(); int z = qZ.Dequeue(); int v = dists[r, c, z]; int nz = z; if (grid0[r, c] == '?') nz = z == 0 ? 1 : 0; char[,] ngrid = nz == 0 ? grid0 : grid1; 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 || ngrid[nr, nc] == '#') continue; if (dists[nr, nc, nz] > v + 1) { dists[nr, nc, nz] = v + 1; qR.Enqueue(nr); qC.Enqueue(nc); qZ.Enqueue(nz); } } } int ans = Math.Min(dists[gr, gc, 0], dists[gr, gc, 1]); Console.WriteLine(ans < int.MaxValue ? ans : -1); } } |
D – Root M Leaper
問題の概要
N × N のマス目がある。
現在位置から距離がちょうど √M であるマスにのみ移動することができる。
(0, 0) にあるマスからそれ以外のマスへの最短経路長を求めよ。
すべてのマスについて、距離がちょうど M であるマスがどれか調べていると TLE してしまいます。そこで 1 つのマスだけ調べてその結果を使い回せばよいです。グリッド上での操作ですが移動先は隣のマスではないので2次元配列を1次元配列に変換して処理をおこなっています。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
class Program { // Bfsメソッドは上記定義のとおり static void Main() { int[] nm = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nm[0]; int M = nm[1]; // (0, 0)にあるマスから移動できるマスを求める List<(int, int)> diffs = new List<(int, int)>(); for (int r = 0; r < N; r++) { for (int c = 0; c < N; c++) { if (r * r + c * c == M) { diffs.Add((r, c)); if(c != 0) diffs.Add((r, -c)); if (r != 0) diffs.Add((-r, c)); if (r != 0 && c != 0) diffs.Add((-r, -c)); } } } // (0, 0)にあるマスから移動できるマスの位置から // (sr, sc)にあるマスから移動できるマスの index をすべて取得する List<int> GetNexts(int sr, int sc) { List<int> res = new List<int>(); foreach (var diff in diffs) { int r = sr + diff.Item1; int c = sc + diff.Item2; if (r < 0 || r >= N || c < 0 || c >= N) continue; res.Add(r * N + c); } return res; } List<int>[] G = new List<int>[N * N]; for (int r = 0; r < N; r++) { for (int c = 0; c < N; c++) { int idx = r * N + c; G[idx] = GetNexts(r, c); } } int[] dists = new int[N * N]; Array.Fill(dists, int.MaxValue); Bfs(G, 0, dists); int[][] ans = new int[N][]; for (int i = 0; i < N; i++) ans[i] = new int[N]; for (int i = 0; i < N * N; i++) { int r = i / N; int c = i % N; ans[r][c] = dists[i] < int.MaxValue ? dists[i] : -1; } foreach (int[] arr in ans) Console.WriteLine(string.Join(" ", arr)); } } |
D – .. (Double Dots)
問題の概要
N 頂点 M 辺の無向グラフが与えられる。
すべての頂点から頂点 1 へたどり着くことはできるだろうか？
できる場合は頂点 1 以外のすべての頂点について、その頂点から移動すべき頂点は何になるかも出力せよ。
始点が N – 1 個あるので時間がかかりそうですが、逆転の発想で頂点 1 を始点に幅優先探索をします。このとき各頂点にはどこから移動してきたのかも記録しておきます。すべての頂点から頂点 1 へたどり着くことができる場合、記録しておいた頂点の番号を出力すればそれが解となります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
class Program { // 幅優先探索（どこから来たのかも記録する） static void Bfs(List<int>[] G, int start, int[] dists, int[] froms) { Queue<int> q = new Queue<int>(); dists[start] = 0; froms[start] = -1; 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; froms[next] = cur; 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[] 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[] dists = new int[N]; Array.Fill(dists, int.MaxValue); int[] froms = new int[N]; Bfs(G, 0, dists, froms); if (!dists.Any(_ => _ == int.MaxValue)) { Console.WriteLine("Yes"); for (int i = 1; i < N; i++) Console.WriteLine(froms[i] + 1); } else Console.WriteLine("No"); } } |
D – Number of Shortest paths
問題の概要
N 頂点 M 辺の無向グラフが与えられる。
頂点 1 から頂点 N までの最短経路は何通りあるか求めよ。
幅優先探索をするさいに各頂点までの最短経路の個数も記録すればよいです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
class Program { // 最短経路長を求めるとともに数え上げもおこなう static void Bfs(List<int>[] G, int start, int[] dists, int[] counts, int mod) { Queue<int> q = new Queue<int>(); dists[start] = 0; counts[start] = 1; 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; counts[next] = counts[cur]; q.Enqueue(next); } else if (dists[next] == dists[cur] + 1) { long sum = 0L + counts[next] + counts[cur]; sum %= mod; counts[next] = (int)sum; } } } } 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[] dists = new int[N]; Array.Fill(dists, int.MaxValue); int[] counts = new int[N]; Bfs(G, 0, dists, counts, (int)Math.Pow(10, 9) + 7); Console.WriteLine(counts[N - 1]); } } |
D – Cycle
問題の概要
N 頂点 M 辺の単純有向グラフがある。
頂点 1 を含む閉路が存在するか判定し、存在する場合はそのような閉路のうち辺数が最小の閉路の辺数を求めよ。
頂点をもうひとつ追加し、これを頂点 N + 1 とします。そして辺が頂点 1 に伸びている場合は頂点 1 ではなく頂点 N + 1 にむけて辺を張ります。頂点 N + 1 までの最短経路長が閉路の辺数です。頂点 1 から頂点 N + 1 へたどり着けない場合は閉路は存在しません。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
class Program { // Bfsメソッドは上記定義のとおり 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 + 1]; for (int i = 0; i < N + 1; 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; if(b != 0) G[a].Add(b); else G[a].Add(N); } int[] dists = new int[N + 1]; Array.Fill(dists, int.MaxValue); Bfs(G, 0, dists); Console.WriteLine(dists[N] < int.MaxValue ? dists[N] : -1); } } |
D – Grid Repainting
問題の概要
マス (1,1) にゲームキャラクター「けぬす君」がいる。
けぬす君は現在位置の上下左右にある白いマスにのみ移動することができる。
ゲームを開始する前にいくつかの白いマス目の色を黒に変えることができる。
けぬす君がマス(H,W) にたどり着けばゲームクリアとなり、ゲームの開始前にマスの色を変えた回数がスコアとなる。
得られるスコアの最大値を求めよ。
(1, 1) から (H, W) にたどり着くために必要なマス以外は黒く塗ってしまってかまいません。黒く塗るマスを最大化するためには塗らずに残すマスは最短経路となるマスです。したがって解は 全体のマスの個数 – 黒マスの個数 – (最短経路長 + 1) です。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
class Program { // GridBfsメソッドは上記定義のとおり 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[,] dists = new int[H, W]; int blackCount = 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] == '.'; blackCount += vs[c] == '#' ? 1 : 0; dists[r, c] = int.MaxValue; } } List<(int r, int c)> starts = new List<(int r, int c)>(); starts.Add((0, 0)); GridBfs(grid, dists, starts); Console.WriteLine(dists[H - 1, W - 1] < int.MaxValue ? H * W - blackCount - (dists[H - 1, W - 1] + 1) : -1); } } |
C – New Skill Acquired
問題の概要
あるゲームには 1 から N の番号がついた N 個のスキルがある。
スキル i は A[i], B[i] の少なくとも一方を習得済みのときのみ習得可能である。
A[i] = 0, B[i] = 0 のときは最初からスキル i は習得済みである。
最初から取得済みのスキルも含め、最終的に習得することができるスキルの個数を求めよ。
頂点 0 から 頂点 N の N + 1 個の頂点を用意します。そして 頂点 A[i] から頂点 i へ、頂点 B[i] から頂点 i へ辺を張ります。これでスキル A[i] またはスキル B[i] を習得しているならスキル i を習得できることが表現できます。
頂点 0 から頂点 0 以外にたどりつくことができる頂点の数が解となります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
class Program { // Bfsメソッドは上記定義のとおり static void Main() { int N = int.Parse(Console.ReadLine()); List<int>[] G = new List<int>[N + 1]; for (int i = 0; i < N + 1; i++) G[i] = new List<int>(); for (int i = 1; i <= N; i++) { int[] ab = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int a = ab[0]; int b = ab[1]; G[a].Add(i); G[b].Add(i); } int[] dists = new int[N + 1]; Array.Fill(dists, int.MaxValue); Bfs(G, 0, dists); int ans = dists.Count(_ => _ < int.MaxValue) - 1; Console.WriteLine(ans); } } |
D – Add One Edge
問題の概要
N1 + N2 頂点 M 辺の無向グラフがある。
頂点 1 から 頂点 N1 までは連結である。
頂点 N1 + 1 から 頂点 N2 までは連結である。
頂点 1 と 頂点 N1 + N2 は連結ではない。
辺をひとつ追加して頂点 1 と 頂点 N1 + N2 が連結となり、最短経路長が最大となるようにしたい。このときの最短経路長を求めよ。
連結成分数が 2 のグラフのなかからふたつの頂点を選んで辺を追加し、連結したグラフをつくる
頂点 1 と頂点 N1 + N2 の最短経路長を最大化するためには、頂点 1 からもっとも離れた頂点と頂点 N1 + N2 からもっとも離れた頂点のあいだに辺を追加すればよいです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
class Program { // Bfsメソッドは上記定義のとおり static void Main() { int[] nm = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N1 = nm[0]; int N2 = nm[1]; int M = nm[2]; List<int>[] G = new List<int>[N1 + N2]; for (int i = 0; i < N1 + N2; 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[] dists = new int[N1 + N2]; Array.Fill(dists, int.MaxValue); Bfs(G, 0, dists); Bfs(G, N1 + N2 - 1, dists); int ans = dists.Take(N1).Max() + dists.Skip(N1).Max() + 1; Console.WriteLine(ans); } } |
C – Ito Campus
問題の概要
うしくん と イノシシ（イノシシは複数いる） が迷路に閉じ込められている。
上下左右に隣接する壁ではないマスにのみ移動できる。
どのイノシシも X 回以下の移動でたどり着くことができないマスを安全なマスと定義する。
うしくんは安全なマスしか通ることができない。
うしくんがスタート地点からゴール地点に到達するまでの最短経路長をもとめよ。
多始点型の幅優先探索でイノシシがたどり着くことができるマスを求めます。それ以外のマスが安全なマスです。安全ではないマスは壁に変更するなどしてもう一度スタート地点を始点に幅優先探索をおこないます。これでゴール地点に到達するまでの最短経路長を求めることができます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
class Program { // Bfsメソッドは上記定義のとおり static void Main() { int[] hwx = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int H = hwx[0]; int W = hwx[1]; int X = hwx[2]; int[,] InitDists() { 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; } return dists; } bool[,] grid = new bool[H, W]; List<(int, int)> starts = new List<(int, int)>(); int sr = 0; int sc = 0; int gr = 0; int 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] == '@') starts.Add((r, c)); if (vs[c] == 'S') { sr = r; sc = c; } if (vs[c] == 'G') { gr = r; gc = c; } } } int[,] dists1 = InitDists(); GridBfs(grid, dists1, starts); for (int r = 0; r < H; r++) { for (int c = 0; c < W; c++) { if (dists1[r, c] <= X) grid[r, c] = false; } } List<(int, int)> starts2 = new List<(int, int)>(); starts2.Add((sr, sc)); int[,] dists2 = InitDists(); GridBfs(grid, dists2, starts2); Console.WriteLine(dists2[gr, gc] < int.MaxValue ? dists2[gr, gc] : -1); } } |
