UVa10908 - Largest Square(DFS)

題目大意：

有一個長方形地圖，會給你一個正方形中心點，此中心點為對角線交叉點，請以此中心點找出最大的正方形，並輸出邊長。

題目連結

重點觀念

• 如何找到最大邊長
• 搜尋是否為正方形
• 英文理解

分析

概念其實很簡單，主要是對中心點向上下延伸伸展出最大的正方形，那要怎麼樣伸展才是最好寫得呢？

可以用一個方式來寫會很好寫，從正方形中心點的左上角開始繞一圈進行搜尋，如果這一圈都是相同字元，那就可以在對下一圈進行搜尋。

直到不能再對下一圈進行搜尋時就輸出最大正方形長度

舉例來說：
紅色點為中心點，而藍色為第一圈、螢光黃色為起頭圍著中心點繞一圈(藍色線段)，只要能夠成功繞一圈那就可以將正方形擴展長度，再從更外面一圈(綠色線條)對中心點圍繞。

心得

這是一個很酷的題目，其實不難但是程式要寫的簡單、概念好懂卻是一個大工夫，我對這題研究大概 40mins，想出了這種最簡單又好寫的程式邏輯。

透過此程式邏輯來寫出此題就快了很多，希望我可以將這些邏輯都應用在未來。

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
using namespace std;
const int MAXN = 120;
int t, q, n, m;
int direct[4][2] = {{0,1},{+1,0},{0,-1},{-1,0}}; //依序是左、下、右、上，圍繞一圈的方向
string graph[MAXN]; //儲存地圖

int isValid(int x, int y){ //判斷這個位置是否非法
    if(x >= 0 && x < m && y >= 0 && y < n) return 1; //判斷此位置是否超出邊界
    return 0;
}

int find_square(int x, int y){//position distance
    int d = 1; //繞圓心一圈的邊長
    int root_char = graph[x][y]; //圓心的字元
    int flag = 1; //判斷這圈是否可以成功繞圓心一圈，1 表示可以、0 表示不行

    while(flag){
        d += 2; //邊長增加兩個丹薇
        int nowX = x-(d/2), nowY = y-(d/2); //找出此圈的左上角點

        for(int i = 0; i < 4; i++){ //四個方向，共繞行一圈
            for(int j = 0; j < d-1; j++){ //每一個方向走 d 步
                nowX += direct[i][0]; //計算當前位置
                nowY += direct[i][1];
                //cout << "nowX nowY " << nowX << ' ' << nowY << ' ' << isValid(nowX,nowY) << '\n';

                if(!isValid(nowX,nowY) || graph[nowX][nowY] != root_char){ //如果是非法位置 || 現在的 now 字元與 root_char 不同
                    flag = 0; //表示無法通行
                    break; 
                }
                //cout << "graph char " << graph[nowX][nowY] << '\n';

            }
            if(flag == 0) break; //如果無法通行則離開
        }
    }
    return d-2; //由於是 d 圈沒辦法繞完，因此 d-2 的距離那圈一定可以繞完。

}

int main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // LOCAL
    cin >> t;
    while(t--){
        cin >> m >> n >> q;
        for(int i = 0; i < m; i++) cin >> graph[i]; //輸入地圖

        cout << m << ' ' << n << ' ' << q << '\n'; //輸出地圖資訊
        int x, y;
        while(q--){ //讀入資訊
            cin >> x >> y; //給予圓心點 x,y
            cout << find_square(x, y) << '\n'; //尋找圓心最大邊長
        }
    }
    return 0;
}