グリッド版ダイクストラ問題セットなのですが、C#の解説がありません。そこで自分で解説をつくることにしました。
コストの合計の最小値
グリッド状の盤面で上下左右の移動を繰り返して、左上から右下まで移動するときに通るマスのコストの合計の最小値を求めよ。
入力例
0 3 1 4 1 5
9 2 6 5 3 5
3 9 7 9 3 2
出力例 17
下記のコードで経路復元の問題とゴールのマスが複数の問題も解くことができます。
|
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 98 99 100 101 102 103 104 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int h, w // 高さと幅が格納されている int[,] map = new int[h, w]; // すでに{ { 0, 3, 1, 4, 1, 5,}, { 9, 2, 6, 5, 3, 5,}, { 3, 9, 7, 9, 3, 2,}, }のように // 配列にデータが格納されているものとする int[,] costs = new int[h, w]; for (int row = 0; row < h; row++) { for (int col = 0; col < w; col++) costs[row, col] = -1; // コストは負数にならないなら-1を代入しておく } // どこから来たのか？ string[,] froms = new string[h, w]; for (int row = 0; row < h; row++) { for (int col = 0; col < w; col++) froms[row, col] = ""; } Queue<int> rows = new Queue<int>(); Queue<int> cols = new Queue<int>(); // スタート位置 rows.Enqueue(0); cols.Enqueue(0); costs[0, 0] = map[0, 0]; while (true) { int row = rows.Dequeue(); int col = cols.Dequeue(); int[] dx = { 1, -1, 0, 0, }; int[] dy = { 0, 0, 1, -1, }; for (int i = 0; i < 4; i++) { int newRow = row + dy[i]; int newCol = col + dx[i]; // 移動不能 if (newRow < 0 || newCol < 0 || newRow >= h || newCol >= w) continue; int cost = costs[row, col] + map[newRow, newCol]; if (costs[newRow, newCol] == -1 || costs[newRow, newCol] > cost) { costs[newRow, newCol] = cost; rows.Enqueue(newRow); cols.Enqueue(newCol); // どこから来たのかも必要であれば保存しておく froms[newRow, newCol] = string.Format("{0} {1}", row, col); } } if (rows.Count == 0) break; } // これが左上から右下まで移動するときに通るマスのコストの合計の最小値を出力する Console.WriteLine(costs[h - 1, w - 1]); // 一番下のマスをゴールとしたときのそれぞれのコストの合計の最小値を出力する for(int i=0; i<w; i++) Console.WriteLine(costs[h - 1, i]); // 経路をゴールからスタートまでの順序で出力する int lastRow = h - 1; int lastCol = w - 1; Console.WriteLine("{0} {1}", lastRow, lastCol); while (true) { if (froms[lastRow, lastCol] == "") break; int[] from = froms[lastRow, lastCol].Split().Select(_ => int.Parse(_)).ToArray(); lastRow = from[0]; lastCol = from[1]; Console.WriteLine("{0} {1}", lastRow, lastCol); } // 各マスのコストを表示する // for (int row = 0; row < h; row++) // { // int[] vs = new int[w]; // for (int col = 0; col < w; col++) // vs[col] = costs[row, col]; // Console.WriteLine(string.Join(",", vs)); // } } } |
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 62 63 64 |
class Program { static void Main() { int h, w // 高さと幅が格納されている int[,] map = new int[h, w]; // すでに配列にデータが格納されているものとする int a = GetMinCost(map, h, w, 0, 0, 0, w - 1); int b = GetMinCost(map, h, w, 0, w - 1, h-1, w - 1); int cost = a + b - map[0, w - 1]; // 同じものを2回数えているので引く Console.WriteLine(cost); } static int GetMinCost(int[,] map, int height, int width, int startRow, int startCol, int goalRow, int goalCol) { int[,] costs = new int[height, width]; for (int row = 0; row < height; row++) { for (int col = 0; col < width; col++) costs[row, col] = -1; } Queue<int> rows = new Queue<int>(); Queue<int> cols = new Queue<int>(); // スタート位置 rows.Enqueue(startRow); cols.Enqueue(startCol); costs[startRow, startCol] = map[startRow, startCol]; while (true) { int row = rows.Dequeue(); int col = cols.Dequeue(); int[] dx = { 1, -1, 0, 0, }; int[] dy = { 0, 0, 1, -1, }; for (int i = 0; i < 4; i++) { int newRow = row + dy[i]; int newCol = col + dx[i]; // 移動不能 if (newRow < 0 || newCol < 0 || newRow >= height || newCol >= width) continue; int cost = costs[row, col] + map[newRow, newCol]; if (costs[newRow, newCol] == -1 || costs[newRow, newCol] > cost) { costs[newRow, newCol] = cost; rows.Enqueue(newRow); cols.Enqueue(newCol); } } if (rows.Count == 0) break; } return costs[goalRow, goalCol]; } } |
マスのコストを0にできるチケット
上下左右の移動を繰り返して左上から右下まで移動するときに通るマスのコストの合計の最小値を求めよ。ただし1 つのマスのコストを 0 にできるチケットを 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 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 |
class Program { static void Main() { int h, w // 高さと幅が格納されている int[,] map = new int[h, w]; // すでに配列にデータが格納されているものとする int ticketCount = // チケットの枚数 int cost = GetMinCostEx(map, h, w, 0, 0, h - 1, w - 1, ticketCount); Console.WriteLine(cost); } static int GetMinCostEx(int[,] map, int height, int width, int startRow, int startCol, int goalRow, int goalCol, int ticketCount) { int[,][] costs = new int[height, width][]; for (int row = 0; row < height; row++) { for (int col = 0; col < width; col++) { costs[row, col] = new int[ticketCount + 1]; for (int i = 0; i < ticketCount + 1; i++) costs[row, col][i] = -1; } } Queue<int> rows = new Queue<int>(); Queue<int> cols = new Queue<int>(); Queue<int> ticketCounts = new Queue<int>(); // スタート位置 rows.Enqueue(startRow); cols.Enqueue(startCol); ticketCounts.Enqueue(ticketCount); costs[startRow, startCol][ticketCount] = map[startRow, startCol]; // スタート位置でチケットを使うことができる if (ticketCount > 0) { rows.Enqueue(startRow); cols.Enqueue(startCol); ticketCounts.Enqueue(ticketCount - 1); costs[startRow, startCol][ticketCount-1] = 0; } while (true) { int row = rows.Dequeue(); int col = cols.Dequeue(); int ticket = ticketCounts.Dequeue(); //Console.WriteLine("{0},{1} {2}", row, col, ticket); int[] dx = { 1, -1, 0, 0, }; int[] dy = { 0, 0, 1, -1, }; for (int i = 0; i < 4; i++) { int newRow = row + dy[i]; int newCol = col + dx[i]; // 移動不能 if (newRow < 0 || newCol < 0 || newRow >= height || newCol >= width) continue; int cost = costs[row, col][ticket] + map[newRow, newCol]; if (costs[newRow, newCol][ticket] == -1 || costs[newRow, newCol][ticket] > cost) { costs[newRow, newCol][ticket] = cost; rows.Enqueue(newRow); cols.Enqueue(newCol); ticketCounts.Enqueue(ticket); } if (ticket > 0) { cost = costs[row, col][ticket]; if (costs[newRow, newCol][ticket-1] == -1 || costs[newRow, newCol][ticket - 1] > cost) { costs[newRow, newCol][ticket - 1] = cost; rows.Enqueue(newRow); cols.Enqueue(newCol); ticketCounts.Enqueue(ticket - 1); } } } if (rows.Count == 0) break; } return costs[goalRow, goalCol].Min(); } } |
経由地の最大コストの最小値
左上から右下まで通るマスのコストの最大値が最小になるような経路で移動し、そのコストの最大値を出力せよ。
コストの計算方法を変えるだけ。ループのなかで costs[row, col], map[newRow, newCol]のうち大きい方をコストとして、これが移動先のコスト小さい場合は書き換えます。ゴールに到達したときのコストが求めるべき答えとなります。
|
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 |
class Program { static int GetMaxCost(int[,] map, int height, int width, int startRow, int startCol, int goalRow, int goalCol) { int[,] costs = new int[height, width]; for (int row = 0; row < height; row++) { for (int col = 0; col < width; col++) costs[row, col] = -1; } Queue<int> rows = new Queue<int>(); Queue<int> cols = new Queue<int>(); // スタート位置 rows.Enqueue(startRow); cols.Enqueue(startCol); costs[startRow, startCol] = map[startRow, startCol]; while (true) { int row = rows.Dequeue(); int col = cols.Dequeue(); int[] dx = { 1, -1, 0, 0, }; int[] dy = { 0, 0, 1, -1, }; for (int i = 0; i < 4; i++) { int newRow = row + dy[i]; int newCol = col + dx[i]; // 移動不能 if (newRow < 0 || newCol < 0 || newRow >= height || newCol >= width) continue; int cost = Math.Max(costs[row, col], map[newRow, newCol]); // ここを変更 if (costs[newRow, newCol] == -1 || costs[newRow, newCol] > cost) { costs[newRow, newCol] = cost; rows.Enqueue(newRow); cols.Enqueue(newCol); } } if (rows.Count == 0) break; } return costs[goalRow, goalCol]; } } |
