import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
def f(u, v):
return u * n + v
n = int(input())
n2 = n * n
dp = [[0] * n2 for _ in range(n2)]
for i in range(n):
s = list(input().rstrip())
for j in range(n):
if s[j] & 1:
dp[f(i, i)][f(j, j)] = 1
for l in range(n):
for r in range(n):
if not max(l, r):
continue
x = max(l, r) + 1
for i in range(n - l):
u = f(i, i + l)
for j in range(n - r):
v = f(j, j + r)
dp0 = x
for y in range(l):
dp0 = min(dp0, dp[f(i, i + y)][v] + dp[f(i + y + 1, i + l)][v])
for y in range(r):
dp0 = min(dp0, dp[u][f(j, j + y)] + dp[u][f(j + y + 1, j + r)])
dp[u][v] = dp0
ans = dp[f(0, n - 1)][f(0, n - 1)]
print(ans)#include<bits/stdc++.h>
#define INT long long
#define x first
#define y second
using namespace std;
const int NN = 55;
const int inf = 1e9 + 7;
const int Md = 650;
typedef pair<int , int> pii;
int n , m , k;
char A[NN][NN];
int dp[NN][NN][NN][NN];
int main(){
#ifndef ONLINE_JUDGE
freopen("in.in","r",stdin);
freopen("out.out","w",stdout);
#endif
int T;
scanf("%d", &n);
for(int i = 1; i <= n; i ++) scanf("%s",A[i] + 1);
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= n; j ++){
if(A[i][j] == '#') dp[i][j][i][j] = 1;
for(int ii = i; ii >= 1; ii --){
for(int jj = j; jj >= 1; jj --){
if(i == ii && j == jj) continue;
dp[i][j][ii][jj] = max(i - ii + 1 , j - jj + 1);
for(int md = i - 1; md >= ii; md --){
dp[i][j][ii][jj] = min(dp[i][j][ii][jj] , dp[i][j][md + 1][jj] + dp[md][j][ii][jj]);
}
for(int md = j - 1; md >= jj; md --){
dp[i][j][ii][jj] = min(dp[i][j][ii][jj] , dp[i][j][ii][md + 1] + dp[i][md][ii][jj]);
}
}
}
}
}
cout << dp[n][n][1][1] << endl;
return 0;
}
1619B - Squares and Cubes | 1619A - Square String |
1629B - GCD Arrays | 1629A - Download More RAM |
1629C - Meximum Array | 1629D - Peculiar Movie Preferences |
1629E - Grid Xor | 1629F1 - Game on Sum (Easy Version) |
2148. Count Elements With Strictly Smaller and Greater Elements | 2149. Rearrange Array Elements by Sign |
2150. Find All Lonely Numbers in the Array | 2151. Maximum Good People Based on Statements |
2144. Minimum Cost of Buying Candies With Discount | Non empty subsets |
1630A - And Matching | 1630B - Range and Partition |
1630C - Paint the Middle | 1630D - Flipping Range |
1328A - Divisibility Problem | 339A - Helpful Maths |
4A - Watermelon | 476A - Dreamoon and Stairs |
1409A - Yet Another Two Integers Problem | 977A - Wrong Subtraction |
263A - Beautiful Matrix | 180C - Letter |
151A - Soft Drinking | 1352A - Sum of Round Numbers |
281A - Word Capitalization | 1646A - Square Counting |