---
# System prepended metadata

title: Largest Square(UVA10908)
tags: [CPE一顆星必考題]

---

# Largest Square(UVA10908)
## [程式繳交區](https://hackmd.io/@Renektonn/Hyr5Lypdye/edit)
## 題目
[點我](https://onlinejudge.org/external/109/10908.pdf)

## 解題網站
[UVA](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1849)
[ZJ](https://zerojudge.tw/ShowProblem?problemid=e575)

## 演算法
```
1. 處理輸入
2. 讓i從0跑到50，代表正方形的半徑，若超過邊界，或i當半徑沒有成功，輸出2i-1，break
```
:::info
當break前，i-1代表最大半徑，乘2加1後即為正方形邊長，即為2(i-1)+1=2i-1
break一定會觸發，因為50當半徑一定不會成功(grid最大是100×100)，這是程式的設計
:::
## 程式碼
```cpp=
/*
1. 處理輸入
2. 讓i從0跑到50，代表正方形的半徑，若超過邊界，或i當半徑沒有成功，輸出2i-3，break
*/
#include <bits/stdc++.h>
using namespace std;
char arr[100][100];

int isValid (int r, int c, int radius) {
    char ch = arr[r][c];
    int up = r - radius, down = r + radius, left = c - radius, right = c + radius;
    for (int i = up; i <= down; i++) {
        for (int j = left; j <= right; j++) {
            if (ch != arr[i][j]) return 0;
        }
    }
    return 1;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int m, n, q;
        cin >> m >> n >> q;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                cin >> arr[i][j];
            }
        }
        cout << m << " " << n << " " << q << endl;
        for (int i = 1; i <= q; i++) {
            int r, c;
            cin >> r >> c;
            if (r < 0 or r >= m or c < 0 or c >= n) {
                cout << 0 << endl;
                continue;
            }
            for (int j = 0; j <= 50; j++) {
                if (r - j < 0 or  r + j >= m or c - j < 0 or c + j >= n or !isValid(r, c, j)) {
                    cout << 2 * j - 1 << endl;
                    break;
                }
            }
        }
    }
    return 0;
}
```