using System; using System.Globalization; class Program { public static void Main(string[] args) { var n = int.Parse(Console.ReadLine()); string[] texts = new string[n]; for (int i = 0; i < n; i++) { texts[i] = Console.ReadLine(); } char[,] grid = new char[n,n]; for (int i = 0; i < n; i++) { for (int k = 0; k < n; k++) { grid[i, k] = texts[i][k]; } } var max = Dfs(grid, 0, 0, n); Console.WriteLine(max.ToString(CultureInfo.InvariantCulture)); } private static int Dfs(char[,] grid, int x, int y, int n) { if (y == n ) { var winCounts = new int[n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (grid[j, i] == 'o') { winCounts[j]++; } } } var values = new Tuple[n]; for (int i = 0; i < n; i++) { values[i] = new Tuple(i, winCounts[i]); } Array.Sort(values, (tuple, tuple1) => tuple1.Item2.CompareTo(tuple.Item2)); int rank = 0; int previous = int.MaxValue; for (int i = 0; i < n; i++) { if (previous > values[i].Item2) { rank++; } if (values[i].Item1 == 0) { return rank; } previous = values[i].Item2; } throw new Exception(); } if (x == n) { return Dfs(grid, 0, y + 1, n); } if (grid[y, x] != '-') { return Dfs(grid, x + 1, y, n); } grid[y, x] = 'o'; grid[x, y] = 'x'; int first = Dfs(grid, x + 1, y, n); grid[y, x] = 'x'; grid[x, y] = 'o'; int second = Dfs(grid, x + 1, y, n); grid[y, x] = '-'; grid[x, y] = '-'; return Math.Min(first, second); } }