백준 2583 영역구하기 //int dfs , ny>=mn체크 , 좌표를배열로바꾸기

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

2583번: 영역 구하기

 

1.int dfs => 영역안의 원소가 몇개인지 카운팅

2.ny>m,n 둘중 뭐쓸지 확실하게

3.좌표를 배열로 바꾸기

#include <bits/stdc++.h>
using namespace std;

#define y1 aaaa

const int max_n = 104;
int m,n,k, ny, nx, ans, a[max_n][max_n], visited[max_n][max_n];
int dx[] = { -1,0,1,0 };
int dy[] = { 0,-1,0,1 };
vector<int> ret;
/*
* dfs
* 1.방문처리
* 2.for(dy,dx)
* 3.방문가능 and 미방문 -> dfs(there)
*
*/

//ny>=n이 아니라 ny=>m!
//ny>=n으로 되잇어서 하루종일 버그찾다가...

/*
* int dfs
* ret=ret+dfs()  =>  영역이 몇개인지 누적합구함
*/
int dfs(int y, int x)
{
	visited[y][x] = 1;
	int ret = 1;

	for (int i = 0; i < 4; ++i)
	{
		ny = y + dy[i];
		nx = x + dx[i];
		if (ny < 0 || nx < 0 || ny >= m || nx >= n) continue;
		//if (a[ny][nx]==1) continue;

		if (a[ny][nx] ==0 && visited[ny][nx] == 0)
			ret=ret+dfs(ny, nx);

	}
	return ret;
}

int main()
{
	cin >> m>>n>>k;

	/*
	* 좌표를 배열로 바꾸는힘
	* : 뒤좌표-1까지만 색칠하면됨
	*/
	for (int i = 0; i < k; ++i)
	{
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;

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


	//0,0부터 구역탐색은 dfs
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			//if (i == 4 && j == 0) cout << a[i][j] << " " << visited[i][j]<<"\n";
			if (a[i][j] !=1 && visited[i][j] == 0) {
				//dfs(i, j); ret++;
				//cout << "dfs : " << i << " " << j << "\n";
				ret.push_back(dfs(i, j));
			}
		}
	}

	cout << ret.size() << "\n";
	sort(ret.begin(), ret.end());
	for (int a : ret) cout << a << " ";

}