fork download
copy 
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4.  
  5. public class Test
  6. {
  7. 	public static void Main()
  8. 	{
  9. 		string textmap = @"煩悩煩悩煩煩悩煩
  10.                            煩煩悩空悩悩悩悩
  11.                            悩空悩空悩空悩煩
  12.                            空煩煩悩悩悩煩煩
  13.                            悩悩悩煩悩煩煩悩
  14.                            煩悩空空悩煩悩煩
  15.                            煩煩煩悩煩空悩煩";
  16.  
  17.         Console.WriteLine("鐘の数は{0}個です.", Func160(textmap));
  18. 	}
  19.  
  20. 	public static int Func160(string textmap)
  21.     {
  22.         //8方向
  23.         var dirs = Enumerable.Range(0, 9).Where(x => x != 4).Select(x => new { X = x % 3 - 1, Y = x / 3 - 1 });
  24.  
  25.         //テキストマップをint配列に変換
  26.         var lines = textmap.Split(new[] { Environment.NewLine, " " }, StringSplitOptions.RemoveEmptyEntries).ToArray();
  27.         var width = lines.Max(x => x.Length);
  28.         var height = lines.Length;
  29.         var N = width * height;
  30.         var tmp = new int[height, width];
  31.         for (var i = 0; i < height; i++)
  32.         {
  33.             var line = lines[i];
  34.             for (var j = 0; j < width; j++)
  35.             {
  36.                 var letter = line.Substring(j, 1);
  37.                 tmp[i, j] = letter == "煩" ? 1 : letter == "悩" ? 2 : 0;
  38.             }
  39.         }
  40.  
  41.         //int配列を隣接リスト形式の有向グラフに変換
  42.         //煩⇒悩をエッジとし、ソースとシンクを追加しておく
  43.         //ソースから辺が伸びているノードのリスト
  44.         var src = new bool[N];
  45.         //ノード間の隣接リスト
  46.         var map = new int[N, 8];
  47.         //シンクへ辺が伸びているノードのリスト
  48.         var snk = new bool[N];
  49.         for (int i = 0; i < height; i++)
  50.         {
  51.             for (int j = 0; j < width; j++)
  52.             {
  53.                 var nIndex = 0;
  54.                 var isAdded = false;
  55.                 foreach (var dir in dirs)
  56.                 {
  57.                     var x = j + dir.X;
  58.                     var y = i + dir.Y;
  59.                     if (tmp[i, j] == 1 && x >= 0 && y >= 0 && x < width && y < height && tmp[y, x] == 2)
  60.                     {
  61.                         if (!isAdded)
  62.                         {
  63.                             isAdded = true;
  64.                             src[i * width + j] = true;
  65.                         }
  66.                         map[i * width + j, nIndex++] = y * width + x;
  67.                         snk[y * width + x] = true;
  68.                     }
  69.                 }
  70.                 for (; nIndex < 8; nIndex++)
  71.                     map[i * width + j, nIndex] = -1;
  72.             }
  73.         }
  74.  
  75.         //対象グラフは2部グラフなので最小カバー=最大フロー
  76.         //なので最大フローを求める
  77.         var result = 0;
  78.         var isChanged = false;
  79.         do
  80.         {
  81.             isChanged = false;
  82.             var isVisited = new bool[N];
  83.             //ソースに隣接した各ノードから深さ優先探索
  84.             for (var i = 0; i < N; i++)
  85.             {
  86.                 if (!src[i] || isVisited[i])
  87.                     continue;
  88.                 isVisited[i] = true;
  89.                 var stack = new Stack<int>();
  90.                 stack.Push(i);
  91.                 while (stack.Count > 0)
  92.                 {
  93.                     var node = stack.Peek();
  94.                     //経路を発見
  95.                     if (snk[node])
  96.                     {
  97.                         isChanged = true;
  98.                         //フローを1増やす
  99.                         result++;
  100.                         src[i] = false;
  101.                         snk[node] = false;
  102.                         stack.Pop();
  103.                         //経路を逆順で処理
  104.                         while (stack.Count > 0)
  105.                         {
  106.                             var prev = stack.Pop();
  107.                             var added = false;
  108.                             for (int j = 0; j < 8; j++)
  109.                             {
  110.                                 //順方向のエッジを削除
  111.                                 if (map[prev, j] == node)
  112.                                 {
  113.                                     for (int k = j; k < 7; k++)
  114.                                         map[prev, k] = map[prev, k + 1];
  115.                                     map[prev, 7] = -1;
  116.                                 }
  117.                                 //残余グラフに逆方向のエッジを追加
  118.                                 if (!added && map[node, j] == -1)
  119.                                 {
  120.                                     added = true;
  121.                                     map[node, j] = prev;
  122.                                 }
  123.                             }
  124.                             node = prev;
  125.                         }
  126.                         //到達情報が変更されたのでリセット
  127.                         Array.Clear(isVisited, 0, N);
  128.                     }
  129.                     //まだ経路が見つかっていない
  130.                     else
  131.                     {
  132.                         var next = -1;
  133.                         for (int j = 0; j < 8; j++){
  134.                             var t = map[node, j];
  135.                             if (t != -1 && !isVisited[t])
  136.                             {
  137.                                 next = t;
  138.                                 break;
  139.                             }
  140.                         }
  141.                         //行き止まりなら1つ戻る
  142.                         if (next == -1)
  143.                             stack.Pop();
  144.                         else
  145.                         {
  146.                             //次があれば進む
  147.                             isVisited[next] = true;
  148.                             stack.Push(next);
  149.                         }
  150.  
  151.                     }
  152.                 }
  153.             }
  154.         } while (isChanged);    //増加路が見つからなくなるまで続ける
  155.  
  156.         return result;
  157.     }
  158. }
Success #stdin #stdout 0.07s 34232KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
鐘の数は22個です.
https://ideone.com/Ao6e7j
language:
C# (gmcs 5.20.1)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!