public class ThreeColorabilityEasy {
int n, m;
int ToIndex(int row, int col) {
return row * (m + 1) + col;
}
List<int>[] ConstrustGraph(string[] cells) {
int nodeNum = (n + 1) * (m + 1);
var graph = Enumerable.Range(0, nodeNum).Select(_ => new List<int>()).ToArray();
var addEdge = new Func<int, int, int, int, int>((r1, c1, r2, c2) => {
graph[ToIndex(r1, c1)].Add(ToIndex(r2, c2));
graph[ToIndex(r2, c2)].Add(ToIndex(r1, c1));
return 0;
});
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
if (i + 1 <= n) addEdge(i, j, i + 1, j);
if (j + 1 <= m) addEdge(i, j, i, j + 1);
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (cells[i][j] == 'N') {
addEdge(i, j, i + 1, j + 1);
} else {
addEdge(i + 1, j, i, j + 1);
}
}
}
return graph;
}
public string isColorable(string[] cells) {
this.n = cells.Length;
this.m = cells[0].Length;
var graph = ConstrustGraph(cells);
var color = new int?[graph.Length];
var qu = new Queue<int>();
if (cells[0][0] == 'N') {
color[ToIndex(0, 0)] = 0;
color[ToIndex(0, 1)] = color[ToIndex(1, 0)] = 2;
} else {
color[ToIndex(0, 1)] = 0;
color[ToIndex(1, 0)] = 1;
color[ToIndex(0, 0)] = 2;
}
qu.Enqueue(ToIndex(1, 1));
while (qu.Any()) {
int now = qu.Dequeue();
if (color[now].HasValue) continue;
var adjacentColors = graph[now].Select(idx => color[idx]).Where(c => c != null).Distinct();
if (adjacentColors.Count() == 3) return "No";
if (adjacentColors.Count() < 2) continue;
color[now] = 6 - adjacentColors.Sum();
foreach (var index in graph[now]) {
if (!color[index].HasValue)
qu.Enqueue(index);
}
}
return "Yes";
}
}