TIL 2018-10-24

오늘 배운 것 & 한 것

---

• algorithm
  • bj 2583 - 영역 구하기.cpp
• dep
• ref

algorithm

bj 2583 - 영역 구하기.cpp

https://www.acmicpc.net/problem/2583

범위가 좁으므로 모든 사각형 범위 읽으면서 1로 만들고, 남은 공간들은 2로 채우면서 영역 배열에 집어넣음.

한가지 헷갈렸던 점은, 사각형의 왼쪽 아래 좌표와 오른쪽 위 좌표를 읽어 1로 채우는 과정에서 for문을 다음과 같이 썼었는데, 잘못된 것이었다.

for(int x = x1; x <= x2; x++){
  for(int y = y1; y <= y2; y++)
  {
    mm[x-1][y-1] = 1;
  }
  
}

for(int x = x1; x <= x2; x++){
  for(int y = y1; y <= y2; y++)
  {
    mm[x][y] = 1;
  }
  
}

왜냐하면, x1,x2,y1,y2가 좌표이므로 x2,y2를 포함하면 하나가 더 포함되는 것이기 때문이다.

위 그림에서 맵의 크기는 가로 5칸, 세로 4칸이므로 map[5][4]이렇게 할당하면 되고, 이것은 오른쪽 위 점 좌표와도 일치한다. 그러나 이 사각형의 점들을 순회할 때는 일차원 배열과 마찬가지로 x=5와 y=4는 제외되어야 한다.

int getArra(int x, int y);

int mm[101][101];
int dx[] = { -1, 0, 0, 1 };
int dy[] = { 0, -1, 1, 0 };
int m, n, k;

void solve()
{
	//cout << "dsddsd" << endl;
	cin >> n >> m >> k;
	//for (int i = 0; i < 101; i++) {
	//	memset(m[i], 0, sizeof(int) * 101);
	//}

	for (int kk = 0; kk < k; kk++)
	{
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		for (int x = x1; x < x2; x++) {
			for (int y = y1; y < y2; y++) {
				mm[x][y] = 1;
			}
		}
	}

	
	int ans = 0;
	vector<int> areas;
	
	for (int x = 0; x < m; x++) {
		for (int y = 0; y < n; y++) {
			if (mm[x][y] == 1 || mm[x][y] == 2) continue;

			ans++;
			areas.push_back(getArra(x, y));

		}
	}

	sort(areas.begin(), areas.end());

	cout << ans << endl;
	int sizee = areas.size();
	for (int r = 0; r < sizee; r++) {
		cout << areas[r] << ' ';
	}
}

int getArra(int x, int y) {
	if (mm[x][y] == 1 || mm[x][y] == 2 || x < 0 || y < 0 || x >= m || y >= n) return 0;

	if (mm[x][y] == 0) {
		int tmp = 0;
		int xx, yy;
		mm[x][y] = 2;
		for (int d = 0; d < 4; d++)
		{
			xx = x + dx[d];
			yy = y + dy[d];
			tmp += getArra(xx, yy);
		}
		return 1 + tmp;
	}
}

dep

ref

---