たくあんポリポリ

勉強したことを載せていきます。最近、技術系の記事はZennに書いています。(https://zenn.dev/chittai)

【C#】BFSを実装する際にQueueに値の組み合わせを入れる方法

AGC033でBFSの実装をしたのですが、Queueに複数の値の組み合わせを格納する方法を学んだのでメモを残します。

atcoder.jp

やりたいこと

この問題では二次元のグリッドが入力として与えられます。"#"の部分は黒で塗りつぶされており、この黒に隣接する上下左右のマスが白かった場合、黒に塗りつぶします。

すべてのマスを黒に塗りつぶす場合、この操作を何回行えばいいか求めます。

解法

問題文から、解法はBFSで実装することが思いつくでしょう。そのためにQueueを使用するのですが、このQueueには黒く塗りつぶされているマスの座標情報を格納する必要があります。

C#の場合Queueは引数を一つしかとれません。 docs.microsoft.com

Tupleを使う

そこで、Tupleを使用します。

docs.microsoft.com

今回の場合だと

Queue<Tuple<int, int>> q = new Queue<Tuple<int, int>>();
q.Enqueue(Tuple.Create(x, y));

とすれば、座標の情報を格納することができます。x,yを取り出すときは下記のようになります。

var t = q.Dequeue();

// x
var x = t.Item1;
// y
var y = t.Item2;

感想

これでグリッド系の問題で座標の情報を格納するときに文字列化したりしなくて済む(アホみたいなことしてる時あったので、、、、)