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;
}