台中女中程式解題系統：b027: 小綠人的城堡

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

題目連結 http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b027。

此題用 Dynamic Programming 可參考 https://leetcode.com/problems/maximal-square/solution/。

主要的演算法如下：
 board[i][j] = min(board[i][j-1], min(board[i-1][j-1], board[i-1][j])) + 1;


程式碼：

1. #include <iostream>    
2.     
3. using namespace std;    
4.     
5. int main()    
6. {    
7.     int board[100][100] = {0};    
8.     int h, w;    
9.     
10.     cin >> h >> w;    
11.   
12.     // 因為題目可蓋城堡是用 0 表示，  
13.     // 所以將 0 變 1、1 變 0，來配合演算法  
14.     for(int i = 0; i < h; i++)    
15.     {    
16.         for(int j = 0; j < w; j++)    
17.         {    
18.             cin >> board[i][j];    
19.             board[i][j] = 1 - board[i][j];    
20.         }    
21.     }    
22.     
23.     int maxSqLen = 0;    
24.     
25.     for(int i = 1; i < h; i++)    
26.     {    
27.         for(int j = 1; j < w; j++)    
28.         {    
29.             if(board[i-1][j-1] >= 1 && board[i][j] == 1)    
30.             {    
31.                 board[i][j] = min(board[i][j-1], min(board[i-1][j-1], board[i-1][j])) + 1;    
32.                 maxSqLen = max(maxSqLen, board[i][j]);    
33.             }    
34.         }    
35.     }    
36.     
37.     int area = maxSqLen * maxSqLen;    
38.     cout << area << endl;    
39.     
40.     return 0;    
41. }