HDU 1838 Chessboard

dp[i][j]表示以(i,j)为右下角所含棋盘的最大规模,

如果 s[i][j] == s[i-1][j-1] && s[i][j] != s[i-1][j] && s[i][j] != s[i][j-1]      dp[i][j] = min( dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1

否则dp[i][j] = 1

 //#define LOCAL
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; int const maxn = + ;
char map[maxn][maxn];
int dp[maxn][maxn]; int main(void)
{
#ifdef LOCAL
freopen("1838in.txt", "r", stdin);
#endif int T;
scanf("%d", &T);
while(T--)
{
int n;
scanf("%d", &n);
int i, j;
for(i = ; i < n; ++i)
scanf("%s", map[i]);
for(i = ; i < n; ++i)
dp[][i] = dp[i][] = ;
int size = , cnt = ;
for(i = ; i < n; ++i)
for(j = ; j < n; ++j)
{
if(map[i][j] == map[i-][j-] && map[i][j] != map[i-][j]
&& map[i][j] != map[i][j-])
dp[i][j] = min(min(dp[i][j-], dp[i-][j]), dp[i-][j-]) + ;
else dp[i][j] = ;
if(map[i][j] == '')
size = max(size, dp[i][j]);
} for(i = ; i < n; ++i)
for(j = ; j < n; ++j)
if(dp[i][j] == size && map[i][j] == '')
++cnt;
printf("%d %d\n", size, cnt);
}
return ;
}

代码君

上一篇:mysql主从数据库


下一篇:停止node进程