Untitled
unknown
plain_text
2 years ago
6.6 kB
6
Indexable
Thống trị khu vực
Cho ma trận NxN (5 ≤ N ≤ 100) chứa các phần tử có giá trị 0 – 5 mô tả lãnh thổ 6 vương quốc. Yêu cầu sáp nhập các vùng số 0 về các lãnh thổ khác sao cho vùng đồng
nhất có diện tích lớn nhất (các vùng được chuyển đổi trước không được tính vào diện tích để quyết định các vùng chuyển đổi sau), sau đó trả về số lượng vùng còn lại sau khi sáp nhập.
Thông thường, chúng ta có thể thấy rõ rằng có hai ô 5, hai ô 4, một ô 3 và hai ô 2 gian hàng xung quanh ba ô 0 này. Tuy nhiên, vì ô 5 cũng kết nối với ô khác cùng loại (ô 5, tại vị trí [1,1] và [4,1] với màu xanh lam), diện tích sẽ trở lên tốt hơn, vì vậy chúng tôi coi tần suất của ô 5 là 4. Trong trường hợp có nhiều hơn một loại ô có cùng tần suất cao nhất, chúng tôi sẽ chọn ô có giá trị cao hơn.
Tiếp tục với ô 0 tiếp theo ta có ma trận bên dưới
Tất cả các Ô cùng loại và cạnh nhau (trên / dưới/ trái / phải) kết nối thành một khu vực.
Ở ví dụ này chúng ta có 11 vùng
[Input]
- Số lượng test case T (T <= 50)
- Kích thước ma trận N (5 <= N <= 100)
- Chi tiết ma trận được cho trong N hàng tiếp theo, Giá trị của mỗi ô có giá trị C (0 <= C <= 5)
5
5
5 5 1 4 4
4 0 2 4 2
5 0 0 2 0
5 4 3 0 1
1 3 3 2 1
7
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
5 0 5 0 5 0 5
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
10
1 3 5 1 4 0 0 4 2 1
1 1 2 1 1 0 5 0 2 1
5 0 2 0 4 4 4 0 1 1
0 2 2 4 0 5 4 2 1 3
1 1 2 2 2 3 3 2 1 1
5 1 1 2 0 3 3 2 2 1
3 1 1 1 0 0 1 2 2 5
3 1 4 1 2 0 4 0 0 5
4 0 3 3 1 3 3 0 0 1
5 0 3 1 4 3 3 1 2 3
...
Case #1
11
Case #2
1
Case #3
31
...
[Constraint]
- Tất cả các ô số 0 cạnh nhau (trên/dưới/trái/phải) được tính là 1 khu vực.
- Chỉ có 6 loại ô từ : 0 - 5, ô sô 0 cần được thay đổi thành các số khác từ (1-5)
- Chúng tôi đảm bảo sẽ không có trường hợp nào trong đó tất cả các ô bằng không
- Tất cả các loại ô giống nhau nằm xung quanh nhau được coi là một khu vực.
- Time limit : 3s for 50 TC ( C, C++ 3000 msec, Java 6000 msec)
#include <iostream>
using namespace std;
#define maxn 101
#define maxq 10000000
int n;
int ans;
int map[maxn][maxn];
int area[6];
int vis0[maxn][maxn];
int vis1[maxn][maxn];
int viske[maxn][maxn];
int dienvung[maxn * maxn];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
class queue
{
public:
queue(){
front = rear = -1;
}
bool isFull(){
if(front == maxq - 1)
return true;
return false;
}
bool isEmpty(){
if(rear == front)
return true;
return false;
}
void enQueue(int a){
if(isFull()){
cout << "Queue is Full" << endl;
return;
}
rear++;
arr[rear] = a;
}
int deQueue(){
if(isEmpty()){
cout << "Queue is Empty" << endl;
return 0;
}
front++;
return arr[front];
}
void reset(){
front = rear = -1;
}
private:
int front, rear;
int arr[maxq];
};
void imports(){
cin >> n;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
cin >> map[i][j];
}
}
}
void reset(){
for(int i = 0; i < 6; i++){
area[i] = 0;
}
for(int i = 0; i < maxn; i++){
for(int j = 0; j < maxn; j++){
map[i][j] = 0;
vis0[i][j] = 0;
vis1[i][j] = 0;
viske[i][j] = 0;
}
}
for(int i = 0; i < maxn * maxn; i++){
dienvung[i] = 0;
}
}
queue xm, ym;
queue xa, ya;
void BFS_dem_1_vung(int x, int y){ // dem xem vung lan can diem 0 co bao nhieu chi so
xm.reset();
ym.reset();
xm.enQueue(x);
ym.enQueue(y);
viske[x][y] = 1;
area[map[x][y]]++;
while(!xm.isEmpty()){
int xf = xm.deQueue();
int yf = ym.deQueue();
for(int i = 0; i < 4; i++){
int xt = xf + dx[i];
int yt = yf + dy[i];
if( xt < 1 || xt > n || yt < 1 || yt > n || viske[xt][yt] != 0) // trong bien
continue;
if(map[xt][yt] == map[xf][yf]){
viske[xt][yt] = 1;
area[map[x][y]]++;
xm.enQueue(xt);
ym.enQueue(yt);
}
}
}
}
void BFS_tim0(int x, int y, int dem){
xa.reset();
ya.reset();
xa.enQueue(x);
ya.enQueue(y);
vis0[x][y] = dem;
while(!xa.isEmpty()){
int xf = xa.deQueue();
int yf = ya.deQueue();
for(int i = 0; i < 4; i++){
int xt = xf + dx[i];
int yt = yf + dy[i];
if( xt < 1 || xt > n || yt < 1 || yt > n || vis0[xt][yt] != 0)
continue;
if( map[xt][yt] == 0){
vis0[xt][yt] = dem;
xa.enQueue(xt);
ya.enQueue(yt);
}
else{
if(viske[xt][yt] == 0){
BFS_dem_1_vung(xt, yt);
}
}
}
}
}
void BFS_dem_vung(int x, int y){
xm.reset();
ym.reset();
xm.enQueue(x);
ym.enQueue(y);
vis1[x][y] = 1;
while(!xm.isEmpty()){
int xf = xm.deQueue();
int yf = ym.deQueue();
for(int i = 0; i < 4; i++){
int xt = xf + dx[i];
int yt = yf + dy[i];
if( xt < 1 || xt > n || yt < 1 || yt > n || vis1[xt][yt] != 0 || map[xt][yt] != map[xf][yf])
continue;
vis1[xt][yt] =1;
xm.enQueue(xt);
ym.enQueue(yt);
}
}
}
void exports(int tc){
ans = 0;
int dem = 1;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(map[i][j] == 0 && vis0[i][j] == 0){
for(int k = 0; k < 6; k++){
area[k] = 0;
}
for(int ii = 1; ii <= n; ii++){ // reset mang visit lien ke
for(int jj = 1; jj <= n; jj++){
viske[ii][jj] = 0;
}
}
BFS_tim0(i,j,dem);
int maxs = 0;
int s;
for(int k = 0; k < 6; k++){
if(area[k] >= maxs){
maxs = area[k];
s = k;
}
}
dienvung[dem] = s;
dem++;
}
}
}
for(int i = 1; i <= n; i++){ // dien cac vung bang 0
for(int j = 1; j <= n; j++){
if(vis0[i][j] != 0){
map[i][j] = dienvung[vis0[i][j]];
}
}
}
for(int i = 1; i <= n; i++){ // dem so vung
for(int j = 1; j <= n; j++){
if( vis1[i][j] == 0){
BFS_dem_vung(i,j);
ans++;
}
}
}
cout << "Case #" << tc << endl;
cout << ans << endl;
}
int main(){
freopen("input.txt","r",stdin);
int t;
cin >> t;
for(int tc = 1; tc <= t; tc++){
reset();
imports();
exports(tc);
}
return 0;
}Editor is loading...