phone s6

 avatar
duyvan
plain_text
7 months ago
3.7 kB
7
Indexable
Never
/*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)
*/