Untitled
unknown
plain_text
2 years ago
5.4 kB
5
Indexable
Bộ xử lý di động Maxinos mới được phát triển của Samsung có số ô N x N.
Trong 1 cell có thể có 1 lõi hoặc 1 dây dẫn điện.
Năng lượng điện chạy trên rìa của Maxinos.
Dây kết nối lõi và nguồn chỉ có thể được cài đặt theo một đường thẳng.
Dây không thể giao nhau với nhau.
Tình trạng ban đầu của Maxinos trước khi nối dây được đưa ra như bên dưới.
(Các Lõi bên lề của Maxinos được coi là đã được kết nối với nguồn điện.)
Khi số Lõi tối đa được kết nối với nguồn điện, hãy tìm tổng chiều dài của dây.
Tuy nhiên, nếu có nhiều phương án khác nhau, hãy tìm giá trị nhỏ nhất của tổng chiều dài của dây.
Câu trả lời cho bài tập trên là 12.
[Những hạn chế]
1. 7 ≤ N ≤ 12
2. Số Lõi lớn hơn hoặc bằng 1 và nhỏ hơn hoặc bằng 12 (1 ≤ N ≤ 12).
3. Có thể có Lõi không được kết nối với nguồn, mặc dù người ta có thể cố gắng kết nối nó với nguồn càng nhiều càng tốt.
[Đầu vào]
Dòng đầu tiên chứa T là số lượng test.
Các trường hợp thử nghiệm được đưa ra bắt đầu từ dòng tiếp theo.
Dòng đầu tiên của mỗi test có N, và trong N dòng tiếp theo là điều kiện ban đầu của Maxinos , được cho trong mảng N x N.
0 biểu thị một ô trống và 1 biểu thị Lõi và không có số nào khác được đưa ra.
[Đầu ra]
In ' #tc ' cho mỗi trường hợp kiểm tra và để lại một khoảng trống và in câu trả lời.
(tc đề cập đến một số trường hợp thử nghiệm và nó bắt đầu bằng 1)
Ví dụ đầu vào
Ví dụ đầu ra
3 // Số lượng test, T = 3
7 // TC 1, N = 7
0 0 1 0 0 0 0
0 0 1 0 0 0 0
0 0 0 0 0 1 0
0 0 0 0 0 0 0
1 1 0 1 0 0 0
0 1 0 0 0 0 0
0 0 0 0 0 0 0
9 // TC 2, N = 9
0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 1
1 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 1 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 1
11 // TC 3, N = 11
0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1
0 0 0 1 0 0 0 0 1 0 0
0 1 0 1 1 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0
#1 12 // Đầu ra của TC thứ 1
#2 10 // Đầu ra của TC thứ 2
#3 24 // Đầu ra của TC thứ 3
INPUT
#include<iostream>
#include<conio.h>
// code 100/100
// Backtrack (trả lại visit)
using namespace std;
int tc,n,map[12][12], visited[12][12];
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1}; // trên, phải, xuống, trái
int chip[2][12], minn=987654,cnt=0,dai=0;
bool checkMap(int x, int y){
return (x<n && y<n && x>=0 && y>=0);
}
bool checkHuong (int x, int y, int hgx, int hgy){
int tempx = x+hgx;
int tempy = y+hgy;
while(checkMap(tempx,tempy)){
if(visited[tempx][tempy]==1){
return false;
}
tempx += hgx;
tempy += hgy;
}
return true;
}
void visit(int x, int y, int hgx, int hgy, int val){
int tempx = x+hgx;
int tempy = y+hgy;
dai=0;
while(checkMap(tempx,tempy) && map[tempx][tempy]==0){
dai++;
visited[tempx][tempy]+=val; // đánh dấu ô đã đi qua
tempx += hgx;
tempy += hgy;
}
}
void BT(int xx,int sum){ // chip, sum
if(sum>minn) return;
if(xx==cnt){
if(sum<minn) minn=sum;
return;
}
int x=chip[0][xx];
int y=chip[1][xx];
if(x==-1 && y==-1){ // chip(-1,-1) là ko thể nối nguồn
BT(xx+1,sum);
}
else{
for(int i=0;i<4;i++){ // đi 4 hướng
if(checkHuong(x,y,dx[i],dy[i]) ){
visit(x,y,dx[i],dy[i],1);
BT(xx+1,sum+dai);
visit(x,y,dx[i],dy[i],-1); // trả lại visit
}
}
return;
}
}
int main(){
freopen("input.txt","r",stdin);
cin>>tc;
for(int t=1;t<=tc;t++){
cin>>n;
minn=987654;
cnt=0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
visited[i][j]=0;
cin>>map[i][j];
if(map[i][j]==1){
if(i==0 || i==n-1 || j==0 ||j==n-1){}
else { // chỉ lưu các chip trong bo
chip[0][cnt]=i;
chip[1][cnt]=j;
cnt++;
}
visited[i][j]=1;
}
}
}
for(int i=0;i<cnt;i++){ // check tất cả các chip theo 4 hướng
bool ch[4];
for(int j=0;j<4;j++){ // check 4 hướng cửa chip
ch[j]=checkHuong(chip[0][i],chip[1][i],dx[j],dy[j]);
}
if(!ch[0] && !ch[1] && !ch[2] && !ch[3] ){ // chip ko đi được hướng nào cả
chip[0][i]=-1;
chip[1][i]=-1;
}
}
BT(0,0);
if(minn==987654) cout<<"#"<<t<< " "<<0<<endl;
else {
cout<<"#"<<t<<" "<<minn<<endl;
}
}
getch();
return 0;
}
Editor is loading...