Untitled
unknown
plain_text
a year ago
7.6 kB
39
Indexable
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
int N,A[101][101],visit[101][101],mang[6],A1[101][101];
int f,r,mQ[500000],mQx1[100000],mQy1[10000],f1,r1;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
void push(int x){
r++;
mQ[r]=x;
}
int pop(){
f++;
return mQ[f];
}
void push1(int x,int y){
r1++;
mQx1[r1]=x;mQy1[r1]=y;
}
void pop1(int &x,int &y){
f1++;
x= mQx1[f1];y=mQy1[f1];
}
void reset(){
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){
visit[i][j]=0;
}
}
for(int i=1;i<=5;i++){
mang[i]=0;
}
}
void input(){
cin>>N;
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){
cin>>A[i][j];visit[i][j]=0;
A1[i][j]=A[i][j];
}
}
}
int timid(){
int id=0;
for(int i=1;i<=5;i++){
if(mang[id]<=mang[i]) id=i;
}
return id;
}
void BFS1(int a){
f1=-1;
while(f1!=r1){
int x,y;
pop1(x,y);
if(A[x][y]==a){
for(int i=0;i<4;i++){
int xx=x+dx[i];
int yy=y+dy[i];
if(xx<1||xx>N||yy<1||yy>N||visit[xx][yy]!=0||A[xx][yy]!=a) continue;
push1(xx,yy);
visit[xx][yy]=1;
mang[A[xx][yy]]++;
}
}
}
}
void BFS(int a,int b,int index){
f=r=-1;r1=-1;
push(a);
push(b);
visit[a][b]=1;
while(f!=r){
int x=pop();
int y=pop();
for(int i=0;i<4;i++){
int xx=x+dx[i];
int yy=y+dy[i];
if(xx<1||xx>N||yy<1||yy>N||visit[xx][yy]!=0) continue;
if(index==0){
if(A[xx][yy]==0){
visit[xx][yy]=1;
push(xx);push(yy);
}else{
push1(xx,yy);
visit[xx][yy]=A[xx][yy];
mang[A[xx][yy]]++;
}
}else{
if(A1[xx][yy]==index){
visit[xx][yy]=1;
push(xx);push(yy);
}
}
}
}
if(index ==0){
int idm;
for(int i=1;i<=5;i++){
BFS1(i);
}
idm=timid();
for(int i=0;i<r;i++){
A1[mQ[i]][mQ[i+1]]=idm;
i++;
}
}
}
int main(int argc, char** argv)
{
int test_case;
int T;
freopen("input.txt", "r", stdin);
cin >> T;
for(test_case = 1; test_case <= T; ++test_case)
{
input();
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){
if(A[i][j]==0&&A1[i][j]==0){
BFS(i,j,0);
reset();
}
}
}
int ans=0;
reset();
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){
if(visit[i][j]==0){
BFS(i,j,A1[i][j]);
ans++;
}
}
}
cout << "Case #" << test_case << endl << ans<< endl;
}
return 0;
}
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
Đổi điện thoại S6
Mẫu Galaxy S6 mới đã được tung ra thị trường. Khách hàng của chúng tôi muốn đổi model cũ (S1 -> S5) sang model mới này.
Hiện tại có một số quầy dịch vụ được định vị trên bản đồ giúp khách hàng đổi máy.
Có tổng cộng 5 loại booth (1->5) giúp đổi máy từ S1->S5 sang model mới.
Tuy nhiên, các gian hàng này được phân phối ngẫu nhiên trên bản đồ.
Bán tại:
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
Ngoài ra còn có các gian hàng phục vụ dịch vụ khác và được đánh dấu là 0 trên bản đồ.
Quản lý của chúng tôi muốn cải thiện dịch vụ cho khách hàng. Để làm được điều đó, chúng ta có thể hoán đổi
buồng 0 thành buồng khác (1-5) xung quanh nó để các buồng cùng loại sẽ được kết nối với nhau. Và để tối đa hóa
hiệu suất, chúng tôi sẽ hoán đổi gian hàng 0 thành gian hàng có tần suất xuất hiện cao nhất xung quanh nó.
Ví dụ: Xét khu vực bao gồm ba gian hàng 0, chúng ta cần hoán đổi các gian hàng này với gian hàng xung quanh
chúng có tần suất xuất hiện cao nhất.
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
Thông thường, chúng ta có thể thấy rõ rằng có hai gian hàng số 5, hai gian hàng số 4, một gian hàng số 3
và hai gian hàng số 2 xung quanh ba gian hàng-0 này. Tuy nhiên, do gian hàng-5 cũng kết nối với gian hàng khác
cùng loại (gian hàng-5, tại vị trí [1,1] và [4,1] có màu xanh lam), dịch vụ có thể trở nên tốt hơn, vì vậy chúng tôi
xem xét tần suất của gian hàng-5 là tổng số 4
Trường hợp có nhiều loại gian hàng có cùng tần suất xuất hiện cao nhất, chúng tôi sẽ chọn gian hàng có giá trị cao hơn
Ví dụ: gian hàng-5 xuất hiện 4 lần, gian hàng-1 cũng xuất hiện 4 lần xung quanh vùng 0, chúng ta sẽ chọn
gian hàng-5 để trao đổi vì 5 > 4
Do đó, chúng tôi sẽ đổi gian hàng-0 thành gian hàng-5 (với tần suất cao nhất)
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
Tiếp tục với booth-0 khác ta sẽ được bản đồ bên dưới
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
Tất cả các gian hàng 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. Sau khi trao đổi xong,
người quản lý của chúng tôi muốn biết có bao nhiêu khu vực dịch vụ trao đổi S6 trong bản đồ này.
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
Trong ví dụ trên, có tổng cộng 11 khu vực (trong mỗi khu vực, chỉ có một dịch vụ được phục vụ)
Cho bản đồ NxN vị trí gian hàng, hãy viết chương trình đổi gian hàng-0 và trả về số khu vực phục vụ trong bản đồ đó.
[Đầu vào]
- Số test case T (T <= 50)
- Kích thước bản đồ N (5 <= N <= 100)
- Chi tiết của bản đồ sẽ được hiển thị ở N hàng tiếp theo, giá trị C của mỗi ô thể hiện gian dịch vụ (0 <= C <= 5)
5 <= Số test case T
5 <= Bắt đầu test case #1, N = 5
5 5 1 4 4 <= Dòng đầu tiên của bản đồ
4 0 2 4 2 <= Dòng thứ hai của bản đồ ...
5 0 0 2 0
5 4 3 0 1
1 3 3 2 1
7 <= Bắt đầu 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
...
[Đầu ra]
- Số vùng dịch vụ
Trường hợp 1
11
Trường hợp #2
1
Trường hợp #3
31
...
[Hạn chế]
- Mỗi gian hàng có tối đa 4 gian hàng xung quanh (trên/dưới/trái/phải)
- Tất cả các gian hàng-0 nằm cạnh nhau (trên/dưới/trái/phải) sẽ được coi là một khu vực, chúng ta cần tính toán tất cả các gian hàng xung quanh khu vực này.
- Có 6 loại gian hàng: 0 - 5, gian hàng 0 cần đổi sang gian hàng khác (1-5)
- Chúng tôi đảm bảo sẽ không có trường hợp tất cả các gian hàng đều bằng 0
- Tất cả các gian hàng cùng loại nằm xung quanh nhau được coi là một khu vực.
- Giới hạn thời gian : 3 giây cho 50 TC ( C, C++ 3000 mili giây, Java 6000 mili giây)