グリッド領域を扱う方法の備忘録 (ABC 430 B-Count Subgrid)

はじめに

私はグリッドを扱うタイプの問題が苦手だ。にも関わらず以前もがき苦しんで出した解法を忘れてしまい、性懲りもなく今回も長く苦しむこととなった。
もうこんな事が無いよう、忘れても良いように対策を書き残す。

結論

グリッド領域が来たらstring[]として扱いましょう。
値を書き換える必要がありそうならchar[][]やchar[,]を使いましょう。

問題

問題はABC 430 B - Count Subgrid。
「B問題だし楽勝やろ」と思って挑んだらグリッドが出てきて固まってしまった。

N×NのグリッドからM×Mの領域を何パターン取り出せるか？
ただし同じ塗られ方は同一として扱う。...という問題設定である。
グリッドはこんな感じで与えられる。

...
###
#.#

回答

このグリッド領域をどう扱えばよいか悩んでいたが、
1行ごとにstring配列として扱えば幸せが訪れると気付いた。

回答

 static void Main(string[] args)
 {
     int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
     int N = input[0];
     int M = input[1];

     // グリッド領域は文字列として扱う
     string[] grid = new string[N];
     for (int i = 0; i < N; i++)
     {
         grid[i] = Console.ReadLine();
     }

     var seen = new HashSet<string>();

     // 左上座標を(r, c)として全探索
     for (int r = 0; r < N - M + 1; r++)
     {
         for (int c = 0; c < N - M + 1; c++)
         {
             var parts = new string[M];
             for (int dr = 0; dr < M; dr++)
             {
                 parts[dr] = grid[r + dr].Substring(c, M); // M×M領域の抜き出し
             }
             string key = string.Join(",", parts);
             seen.Add(key);
         }
     }

     Console.WriteLine(seen.Count);
 }

for文のネストが深い点は気に食わないけど...。

学び

グリッド領域はstring[]で1行ずつ扱うことで、r番目の要素のc文字目が
元のグリッドの(r, c)に対応すると分かった。これさえ分かっていればグリッドは戦えそう。
ただ、値の書き換えを行うような場合だとstringは始末が悪い。
そういうときはcharの方が良さそうではある。