主要的演算法如下:
board[i][j] = min(board[i][j-1], min(board[i-1][j-1], board[i-1][j])) + 1;
程式碼:
board[i][j] = min(board[i][j-1], min(board[i-1][j-1], board[i-1][j])) + 1;
程式碼:
- #include <iostream>
- using namespace std;
- int main()
- {
- int board[100][100] = {0};
- int h, w;
- cin >> h >> w;
- // 因為題目可蓋城堡是用 0 表示,
- // 所以將 0 變 1、1 變 0,來配合演算法
- for(int i = 0; i < h; i++)
- {
- for(int j = 0; j < w; j++)
- {
- cin >> board[i][j];
- board[i][j] = 1 - board[i][j];
- }
- }
- int maxSqLen = 0;
- for(int i = 1; i < h; i++)
- {
- for(int j = 1; j < w; j++)
- {
- if(board[i-1][j-1] >= 1 && board[i][j] == 1)
- {
- board[i][j] = min(board[i][j-1], min(board[i-1][j-1], board[i-1][j])) + 1;
- maxSqLen = max(maxSqLen, board[i][j]);
- }
- }
- }
- int area = maxSqLen * maxSqLen;
- cout << area << endl;
- return 0;
- }
沒有留言:
張貼留言