2011-06-16 18:20:38Morris
d729. 10593 - Kites
http://zerojudge.tw/ShowProblem?problemid=d729
內容 ：
給你一個正方形的紙，本身可能有很多洞。你的任務是算出這張紙可以剪成多少種箏形和正方形(任意大小) ，當然剪下來的圖形不能有洞。
x
x xxx xxx xxx
xxx xxxxx xxx x.x x
x xxx xxx xxx
x
上面前三個剪下來圖形是符合的，後面兩個是不符合的。
輸入說明 ：
輸入第一個數為n (n ≤ 500)，代表正方形紙張的邊長。接下來n行每行有n個字元('x' or '.')。'.'代表紙張上的洞 。檔案以EOF結束。
輸出說明 ：
輸出為一行，代表能剪下幾種圖形。
範例輸入 ：
4.xx.xxxx.xx..x..3xxxxxxxxx
範例輸出 ：
46
提示 ：
出處 ：
UVA 10593 (管理：asas)
作法 : DP
UVA那邊的線上討論區講的，都看不懂啊 ...
正方形的效率 O(N*N)
筝形的效率 O(N*N)
這兩者其實是一樣的，只是差了 45 度角，DP的模式，就轉個方式跑就好了
要找多少正方形，我們先將問題轉換
找出每一個點(以它為右下角的最大正方形)，只要知道最大正方形的大小
假使是 3*3 那必然有 2*2 1*1 ...
我們只要將所有點能夠成最大正方形的邊長加總就是答案了
那，如何用DP找出以此點為右下角的最大正方形
我們可以很明顯的發現，這點的構成，跟左上角，上方，左方，
這三點能夠成的最大正方形有關，取最小的，在加 1
如上圖，藍色是待測點，紫綠紅三點是已知點，分別是 2 2 4
那麼最小值 2，能構成的就是 3*3的正方形
剩下，請自行思考
跑的方式，如上
筝形也類同
藍色只要判斷是否為'x' 即可
作法 : DP
UVA那邊的線上討論區講的，都看不懂啊 ...
正方形的效率 O(N*N)
筝形的效率 O(N*N)
這兩者其實是一樣的，只是差了 45 度角，DP的模式，就轉個方式跑就好了
要找多少正方形，我們先將問題轉換
找出每一個點(以它為右下角的最大正方形)，只要知道最大正方形的大小
假使是 3*3 那必然有 2*2 1*1 ...
我們只要將所有點能夠成最大正方形的邊長加總就是答案了
那，如何用DP找出以此點為右下角的最大正方形
我們可以很明顯的發現，這點的構成，跟左上角，上方，左方，
這三點能夠成的最大正方形有關，取最小的，在加 1
如上圖，藍色是待測點，紫綠紅三點是已知點，分別是 2 2 4
那麼最小值 2，能構成的就是 3*3的正方形
剩下，請自行思考
跑的方式，如上
筝形也類同
藍色只要判斷是否為'x' 即可
/**********************************************************************************/
/* Problem: d729 "10593 - Kites" from UVA 10593 */
/* Language: C */
/* Result: AC (532ms, 1008KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-16 16:44:21 */
/**********************************************************************************/
#include<stdio.h>
char Map[502][502] = {};
short DP[502][502] = {};
short min(short x, short y) {
if(x < y) return x;
return y;
}
int Calu_square(int n) {
int a, b, Ans = 0;
short t1, t2, t3;
/*store (x,y) MaxL square，(x, y) is Lower right corner of the square*/
for(a = 1; a <= n; a++)
for(b = 1; b <= n; b++) {
if(Map[a][b]) {
t1 = 0, t2 = 0, t3 = 0;
if(Map[a-1][b-1])
t1 = (DP[a-1][b-1] > 1) ? DP[a-1][b-1] : 1;
if(Map[a][b-1])
t2 = (DP[a][b-1] > 1) ? DP[a][b-1] : 1;
if(Map[a-1][b])
t3 = (DP[a-1][b] > 1) ? DP[a-1][b] : 1;
t1 = min(min(t1, t2), t3);
if(t1) {
DP[a][b] = t1+1;
Ans += t1;
}
else DP[a][b] = 0;
}
}
return Ans;
}
int Calu_rhombus(int n) {
int a, b, c, Ans = 0;
short t1, t2, t3;
for(a = 1; a <= n; a++)
for(c = a, b = 1; c >= 1; c--, b++) {
if(Map[c][b]) {
t1 = 0, t2 = 0, t3 = 0;
if(Map[c-1][b-1])
t1 = (DP[c-1][b-1] > 1) ? DP[c-1][b-1] : 1;
if(b-2 > 0&& Map[c][b-2])
t2 = (DP[c][b-2] > 1) ? DP[c][b-2] : 1;
if(Map[c+1][b-1])
t3 = (DP[c+1][b-1] > 1) ? DP[c+1][b-1] : 1;
t1 = min(min(t1, t2), t3);
if(Map[c][b-1]) {
DP[c][b] = t1+1;
Ans += t1;
}
else DP[c][b] = 1;
}
}
for(a = 2; a <= n; a++)
for(c = n, b = a; c >= 1 && b <= n; c--, b++) {
if(Map[c][b]) {
t1 = 0, t2 = 0, t3 = 0;
if(Map[c-1][b-1])
t1 = (DP[c-1][b-1] > 1) ? DP[c-1][b-1] : 1;
if(b-2 > 0&& Map[c][b-2])
t2 = (DP[c][b-2] > 1) ? DP[c][b-2] : 1;
if(Map[c+1][b-1])
t3 = (DP[c+1][b-1] > 1) ? DP[c+1][b-1] : 1;
t1 = min(min(t1, t2), t3);
if(Map[c][b-1]) {
DP[c][b] = t1+1;
Ans += t1;
}
else DP[c][b] = 1;
}
}
return Ans;
}
main() {
int n, a, b;
char s[501];
while(scanf("%d", &n) == 1) {
getchar();
for(a = 0; a <= n+1; a++)
for(b = 0; b <= n+1; b++)
Map[a][b] = 0, DP[a][b] = 0;
for(a = 1; a <= n; a++) {
gets(s);
for(b = 1; b <= n; b++)
Map[a][b] = (s[b-1] == 'x');/*x 1 . 0*/
}
printf("%d\n", Calu_rhombus(n)+Calu_square(n));
}
return 0;
}