#include #include using namespace std; #define N 6 int n; char s[N][N]; int rank() { int w[N] = { 0, }; for ( int i = 0; i < n; i++ ) { for ( int j = 0; j < n; j++ ) { w[i] += s[i][j] == 'o' ? 1 : 0; } } int t[N] = { 0, }; for ( int i = 0; i < n; i++ ) { t[w[i]] = 1; } int r = 0; for ( int i = w[0]; i < n; i++ ) { r += t[i]; } return r; } int dfs(int a, int b, int r, int rg) { s[a][b] = r ? 'o' : 'x'; s[b][a] = r ? 'x' : 'o'; int mn = N; if ( rg == 1 ) { mn = ::rank(); } else { int t = b; for ( int i = a; i < n - 1; i++ ) { for ( int j = t + 1; j < n; j++ ) { if ( s[i][j] == '-' ) { int r1 = dfs(i, j, 1, rg - 1); if ( r1 == 1 ) { return 1; } int r2 = dfs(i, j, 0, rg - 1); if ( r2 == 1 ) { return 1; } mn = min(min(r1, r2), mn); } } t = i + 1; } } s[a][b] = s[b][a] = '-'; return mn; } int main() { int rg = 0; cin >> n; for ( int i = 0; i < n; i++ ) { for ( int j = 0; j < n; j++ ) { cin >> s[i][j]; rg += s[i][j] == '-' ? 1 : 0; } } rg /= 2; if ( rg == 0 ) { cout << ::rank() << endl; return 0; } for ( int i = 0; i < n - 1; i++ ) { for ( int j = i + 1; j < n; j++ ) { if ( s[i][j] == '-' ) { int r1 = dfs(i, j, 1, rg); cout << (r1 == 1 ? 1 : min(r1, dfs(i, j, 0, rg))) << endl; return 0; } } } return 0; }