首页 > 代码库 > HDU 1838 Chessboard
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
1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7 8 int const maxn = 2000 + 5; 9 char map[maxn][maxn];10 int dp[maxn][maxn];11 12 int main(void)13 {14 #ifdef LOCAL15 freopen("1838in.txt", "r", stdin);16 #endif17 18 int T;19 scanf("%d", &T);20 while(T--)21 {22 int n;23 scanf("%d", &n);24 int i, j;25 for(i = 0; i < n; ++i)26 scanf("%s", map[i]);27 for(i = 0; i < n; ++i)28 dp[0][i] = dp[i][0] = 1;29 int size = 1, cnt = 0;30 for(i = 1; i < n; ++i)31 for(j = 1; j < n; ++j)32 {33 if(map[i][j] == map[i-1][j-1] && map[i][j] != map[i-1][j] 34 && map[i][j] != map[i][j-1])35 dp[i][j] = min(min(dp[i][j-1], dp[i-1][j]), dp[i-1][j-1]) + 1;36 else dp[i][j] = 1;37 if(map[i][j] == ‘1‘)38 size = max(size, dp[i][j]);39 }40 41 for(i = 0; i < n; ++i)42 for(j = 0; j < n; ++j)43 if(dp[i][j] == size && map[i][j] == ‘1‘)44 ++cnt;45 printf("%d %d\n", size, cnt);46 }47 return 0;48 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。