---
# System prepended metadata

title: UVA 10908 Largest Square

---

# UVA 10908 Largest Square
##  題目連結 [UVA 10908](https://vjudge.net/problem/UVA-10908)
### 題目內容
Given a rectangular grid of characters you have to find out the length of a side of the largest square such that all the characters of the square are same and the center [intersecting point of the two diagonals] of the square is at location (r, c). The height and width of the grid is M and N respectively. Upper left corner and lower right corner of the grid will be denoted by (0, 0) and (M − 1, N − 1) respectively. Consider the grid of characters given below. Given the location (1, 2) the length of a side of the largest square is 3.
abbbaaaaaa
abbbaaaaaa
abbbaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaccaaaaaa
aaccaaaaaa
### 輸入限制
The input starts with a line containing a single integer T (< 21). This is followed by T test cases. The first line of each of them will contain three integers M, N and Q (< 21) separated by a space where M, N denotes the dimension of the grid. Next follows M lines each containing N characters. Finally, there will be Q lines each containing two integers r and c. The value of M and N will be at most 100.
### 輸出限制
For each test case in the input produce Q + 1 lines of output. In the first line print the value of M, N and Q in that order separated by single space. In the next Q lines, output the length of a side of the largest square in the corresponding grid for each (r, c) pair in the input.
### 解題思路
1.先創一個字串陣列
2.ans初始等於1是因為剛開始中心點已經算進去了，i為往外擴散的大小，i不能超過m或n ，ty為判斷是否超過邊界或周圍是否有不同於中心點的字元
3.r-i ~ r+i與c-i ~ c+i會算到中心點擴散的8個點
### 程式碼
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;
    string map[105];
    cin>>t;
    while(t--){
        int n,m,q;
        cin>>n>>m>>q;
        for(int i=0;i<n;i++){
            cin>>map[i];
        }
        cout<<n<<" "<<m<<" "<<q<<endl;
        while(q--){
            int r,c,ans=1;
            cin>>r>>c;
            for(int i=1;i<n||i<m;i++){
                int ty=1;
                for(int j=r-i;j<=r+i;j++){
                    for(int k=c-i;k<=c+i;k++){
                        if(j<0||j>=n||k<0||k>=m){
                            ty=0;
                            break;
                        }
                        if(map[j][k]!=map[r][c]){
                            ty=0;
                            break;
                        }
                    }
                }
                if(ty==1){
                    ans+=2;
                }
                else{
                    break;
                }
            }
            cout<<ans<<endl;
        }
    }
}
```
## 測資
### Sample input
1
7 10 4
abbbaaaaaa
abbbaaaaaa
abbbaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaccaaaaaa
aaccaaaaaa
1 2
2 4
4 6
5 2
### Sample output
7 10 4
3
1
5
1
##  中文題目連結 [zerojudge e575](https://zerojudge.tw/ShowProblem?problemid=e575)