台中女中程式解題系統: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. }   

沒有留言: