Untitled
unknown
plain_text
2 years ago
6.5 kB
9
Indexable
Trade-in Phone S6
New model Galaxy S6 has been released on market. Our customers want to change their old models (S1 -> S5) to this new model. Currently, there are several service booths locate on map to help customer change their device.
There are total 5 kinds of booth (1->5) to help change device from S1->S5 to new model. However, these booth were distributed randomly on the map.
Ex:
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
There are also the booths which serve other service and are marked as 0 on the map.
Our manager wants to improve the service for customers. To do that, we can exchange the booth 0 to other booth (1-5) around it so that the same kind of booths will be connected. And in order to maximum the performance, we will exchange booth 0 to the booth with highest frequency of appearance around it.
Ex: Consider the area consist of three booths 0, we need to exchange these booths to the booth around them with highest appearance frequency.
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
Normally, we can clearly see that there are two booths of 5, two booths of 4, one booth of 3 and two booth of 2 around these three booth-0. However, since the booth-5 also connect to other booth with same kind (booth-5, at location [1,1] and [4,1] with blue color), the service may become better, so we consider the frequency of booth-5 to be total 4
In case there are more than one kind of booths with same highest frequency, we will select the booth with higher value
Ex : booth-5 appear 4 times, booth-1 appear also 4 times around an area of zeros, we will select booth-5 to exchange since 5 > 4
Therefore, we will exchange booth-0 to booth-5 (with highest frequency)
5 5 1 4 4
4 5 2 4 2
5 5 5 2 0
5 4 3 0 1
1 3 3 2 1
Continue with other booth-0, we will get below map
5 5 1 4 4
4 5 2 4 2
5 5 5 2 2
5 4 3 3 1
1 3 3 2 1
All the booths that are same kind and next to each other (top/down/left/right) connect into an area. After exchangings are done, our manager want to know how many area that service trade-in S6 in this map.
5 5 1 4 4
4 5 2 4 2
5 5 5 2 2
5 4 3 3 1
1 3 3 2 1
In above example, there are total 11 areas (in each area, only one service was served)
Given the map NxN of booths location, write a program to exchange booth-0 and return the number of service area in that map.
[Input]
- The number of test case T (T <= 50)
- The size of the map N (5 <= N <= 100)
- Detail of the map will be given at next N rows, the value C of each cell represent the service booth (0 <= C <= 5)
5 <= The number of test case T
5 <= Start of test case #1, N = 5
5 5 1 4 4 <= The first line of map
4 0 2 4 2 <= The second line of map ...
5 0 0 2 0
5 4 3 0 1
1 3 3 2 1
7 <= Start of test case #2, N = 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
[Output]
- The number of service areas
Case #1
11
Case #2
1
Case #3
31
...
[Constraint]
- Each booth has maximum 4 booths around it (top/down/left/right)
- All booth-0 locate next to each others (top/down/left/right) will be consider as an area, we need to calculate all the booths around this area.
- There are 6 kind of booth : 0 - 5, booth 0 need to be changed to one of other (1-5)
- We ensure there will be no case in which all booths are zero
- All the same kind of booths which locate around each other are consider as one area.
- Time limit : 3s for 50 TC ( C, C++ 3000 msec, Java 6000 msec)
Code:
#include<iostream>
#define max 1000000
using namespace std;
int n;
int queue[2][max];
int front =-1 ;
int rear=-1;
int map[105][105];
int mapCop[105][105];
int visit[105][105];
int di[4]={0, 0, 1, -1};
int dj[4]={1,-1, 0, 0};
int ans;
int tanso[6];
void push(int i, int j){
if(rear == max-1) rear =-1;
rear++;
queue[0][rear]=i;
queue[1][rear]=j;
}
void pop(){
if(front == max-1) front =-1;
front++;
}
bool IsEmpty(){
return front == rear;
}
bool checkIn(int i, int j){
if(i>=0 && i < n && j >=0 && j < n) return true;
return false;
}
void Reset() {
front=rear=-1;
for(int i=0; i <105 ; i++){
for(int j=0; j<105; j++){
visit[i][j] =0;
}
}
for(int i=0; i <6 ; i++){
tanso[i]=0;
}
}
void dequy(int i, int j ,int color){
for(int a=0; a<4; a++){
int i2 = i + di[a];
int j2 = j + dj[a];
if(checkIn(i2, j2) && visit[i2][j2] ==0 && map[i2][j2] ==0){
visit[i2][j2] =1;
mapCop[i2][j2] = color;
dequy(i2,j2,color);
}
}
}
void bfs( int i ,int j){
Reset();
push(i,j);
visit[i][j] =1;
while(!IsEmpty()){
pop();
int i1=queue[0][front];
int j1=queue[1][front];
for(int a=0; a<4; a++){
int i2 = i1 + di[a];
int j2 = j1 + dj[a];
if(checkIn(i2, j2) && visit[i2][j2] ==0){
if(map[i1][j1] == 0 || map[i2][j2] == map[i1][j1]){
tanso[map[i2][j2]] ++;
visit[i2][j2]=1;
push(i2,j2);
}
}
}
}
int maxTS = tanso[1], color = 1;
for (int i = 2; i <= 5; i++)
if (tanso[i] >= maxTS) { // Chon ra so co tan so xuat hien nhieu nhat
color = i;
maxTS = tanso[i];
}
mapCop[i][j] = color;
dequy(i, j , color);
}
void Try(){
for(int i=0; i <n ; i++){
for(int j=0; j<n; j++){
if(mapCop[i][j] == 0){
bfs(i,j);
}
}
}
}
void dem(){
Reset();
for(int i=0; i <n ; i++){
for(int j=0; j<n; j++){
if(visit[i][j] ==0){
push(i,j);
visit[i][j] =1;
ans++;
while(!IsEmpty()){
pop();
int i1=queue[0][front];
int j1=queue[1][front];
for(int a=0; a<4; a++){
int i2 = i1 + di[a];
int j2 = j1 + dj[a];
if(mapCop[i2][j2] == mapCop[i1][j1] && visit[i2][j2] == 0) {
visit[i2][j2] =1;
push(i2,j2);
}
}
}
}
}
}
}
int main(){
freopen("Text.txt" ,"r", stdin);
int test;
cin >> test;
for(int tc=1; tc <= test; tc++){
cin >> n ;
for(int i=0; i <105 ; i++){
for(int j=0; j<105; j++){
mapCop[i][j] = map[i][j]=0;
}
}
for(int i=0; i <n ; i++){
for(int j=0; j<n; j++){
cin >> map[i][j];
mapCop[i][j] = map[i][j];
}
}
ans =0;
Try();
dem();
cout << "Case #" << tc << endl;
cout << ans << endl;
}
return 0;
}
Editor is loading...