You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
76 lines
1.5 KiB
C++
76 lines
1.5 KiB
C++
#include <cstdio>
|
|
#include <iostream>
|
|
#include <set>
|
|
#include <cstring>
|
|
#include <utility>
|
|
#include <vector>
|
|
|
|
using std::string;
|
|
|
|
struct block {
|
|
int n;
|
|
int no_connected;
|
|
block* connected[4];
|
|
};
|
|
|
|
void fill(block* b, int n) {
|
|
if (b->n != -1) return;
|
|
b->n = n;
|
|
for(int i = 0; i < b->no_connected; i++) {
|
|
fill(b->connected[i], n);
|
|
}
|
|
}
|
|
|
|
|
|
int main(int argc, char const *argv[])
|
|
{
|
|
int T;
|
|
std::cin >> T;
|
|
for (int i = 0; i < T; ++i)
|
|
{
|
|
int n,m,p,c;
|
|
std::cin >> n;
|
|
std::cin >> m;
|
|
std::cin >> p;
|
|
std::cin >> c;
|
|
block blocks[n][m];
|
|
for(int x = 0; x < n; x++)
|
|
for(int y = 0; y < m; y++) {
|
|
blocks[x][y].n = -1;
|
|
blocks[x][y].no_connected = 0;
|
|
}
|
|
|
|
block* powered[p];
|
|
for(int j = 0; j < p; j++) {
|
|
int x,y;
|
|
std::cin >> x;
|
|
std::cin >> y;
|
|
powered[j] = &blocks[x][y];
|
|
}
|
|
for(int j = 0; j < c; j++) {
|
|
int x,y; char d;
|
|
std::cin >> x;
|
|
std::cin >> y;
|
|
std::cin >> d;
|
|
if (d == 'R') {
|
|
blocks[x][y].connected[blocks[x][y].no_connected++] = &blocks[x+1][y];
|
|
blocks[x+1][y].connected[blocks[x+1][y].no_connected++] = &blocks[x][y];
|
|
} else {
|
|
blocks[x][y].connected[blocks[x][y].no_connected++] = &blocks[x][y+1];
|
|
blocks[x][y+1].connected[blocks[x][y+1].no_connected++] = &blocks[x][y];
|
|
}
|
|
}
|
|
for (int j = 0; j < p; j++) {
|
|
fill(powered[j], 0);
|
|
}
|
|
int cur_groups = 0;
|
|
for(int x = 0; x < n; x++)
|
|
for(int y = 0; y < m; y++) {
|
|
if (blocks[x][y].n == -1) {
|
|
fill(&blocks[x][y], ++cur_groups);
|
|
}
|
|
}
|
|
std::cout << cur_groups << std::endl;
|
|
}
|
|
return 0;
|
|
} |