#include <bits/stdc++.h>
using
namespace
std;
void
traverse(
int
i,
int
j,
int
N,
int
M,
vector<vector<
bool
> >& vis,
vector<vector<
bool
> >& row,
vector<vector<
bool
> >& col)
{
if
(i <= 0 || i > N || j <= 0 || j > M || vis[i][j])
return
;
vis[i][j] =
true
;
if
(row[i][j])
traverse(i, j + 1, N, M,
vis, row, col);
if
(col[i][j])
traverse(i + 1, j, N, M,
vis, row, col);
if
(row[i][j - 1])
traverse(i, j - 1, N, M,
vis, row, col);
if
(col[i - 1][j])
traverse(i - 1, j, N, M,
vis, row, col);
}
int
count(
int
N,
int
M,
int
K,
vector<vector<
int
> >& q)
{
vector<vector<
bool
> > row(N + 1,
vector<
bool
>(
M + 1,
true
));
vector<vector<
bool
> > col(N + 1,
vector<
bool
>(
M + 1,
true
));
vector<vector<
bool
> > vis(N + 1,
vector<
bool
>(
M + 1,
false
));
for
(
int
i = 0; i < K; i++) {
if
(q[i][0] == q[i][2]) {
int
mn = min(q[i][1], q[i][3]);
row[q[i][0]][mn] =
false
;
}
else
{
int
mn = min(q[i][0], q[i][2]);
col[mn][q[i][1]] =
false
;
}
}
int
TotalRegion = 0;
for
(
int
i = 1; i <= N; i++) {
for
(
int
j = 1; j <= M; j++) {
if
(!vis[i][j]) {
TotalRegion++;
traverse(i, j, N, M,
vis, row, col);
}
}
}
return
TotalRegion;
}
int
main()
{
vector<vector<
int
> > q;
int
N = 5, M = 5;
int
K = 10;
q.push_back({ 2, 1, 2, 2 });
q.push_back({ 1, 2, 2, 2 });
q.push_back({ 1, 3, 2, 3 });
q.push_back({ 1, 4, 2, 4 });
q.push_back({ 2, 3, 3, 3 });
q.push_back({ 3, 3, 3, 4 });
q.push_back({ 3, 3, 4, 3 });
q.push_back({ 3, 3, 3, 2 });
q.push_back({ 3, 1, 3, 2 });
q.push_back({ 4, 1, 4, 2 });
cout << count(N, M, K, q);
return
0;
}