def min(a,b); a < b ? a : b; end def max(a,b); a > b ? a : b; end N = gets.to_i B = N.times.map { gets.chomp } W = Array.new(N + 1, 0); W[N] = 1_000_000 Q = [] (0 ... N).each do |i| (i ... N).each do |j| if B[i][j] == 'o' W[i] += 1 elsif B[i][j] == 'x' W[j] += 1 elsif B[i][j] == '-' Q << [i, j] end end end def dfs(i) if i < Q.size Q[i].map do |j| W[j] += 1 s = dfs(i + 1) W[j] -= 1 s end.min else W.select{|w| w > W[0] }.uniq.size end end puts dfs(0)