12882 City Park

題目說明

給定一個平面，以及n塊板子，並告訴你這n塊板子的左下角座標以及寬度長度。 考慮板子之間會相連的情況下，輸出最大板子(相鄰的算同一個板子)的面積。

解題過程

輸入板子的左下角時把座標存進一個List(或vector)中 並儲存到一個很大的整數二維陣列內，其中0代表沒板子，1代表有 輸入完畢後用DFS(或是BFS也可以)來遍歷List，每次遞迴都先檢查自己所在的格子是否為1，是的話就先把所在的格子變成0(紀錄走訪)，並向返回1+四個方向繼續遞迴的值 小技巧:儲存座標可以用string或int的方式確保座標的單一性(利用HashCode的精神)，並且能夠用比struct更少的字數

考點:圖的遍歷，陣列應用

程式碼

#include<iostream>
#include<vector>
using namespace std;
static int arr[50000][50000] = {0};
int DFS(int a, int b) {
    if(arr[a][b] == 0 || a < 0 || b < 0 || a >= 50000 || b >= 50000)
        return 0;
    arr[a][b] = 0;
    return DFS(a, b + 1) + DFS(a, b - 1) + DFS(a + 1, b)+DFS(a - 1,b) + 1;
}
int main() {
    vector<int> v;
    int c, x, y, a, b, ans = 0;
    cin >> c;
    for(;c ;c--){
        cin >> x >> y >> a >> b;
        v.push_back(x * 100000 + y);
        for(int i = 0;i < a; i++)
            for(int j = 0;j < b; j++)
                arr[i + x][j + y] = 1;
    }
    for(int i : v)
        ans = max(ans, DFS(i / 100000, i % 100000));
    cout << ans;
}