# Untitled

unknown
plain_text
a year ago
1.9 kB
3
Indexable
Never
```// In Practice, You should use the statndard input/output
// in order to receive a score properly.
// Do not use file input and output. Please be very careful.
#define _CRT_SECURE_NO_WARNINGS

#include<iostream>

using namespace std;
int const max_size =15;
int map[15][15];
int core[max_size][2];
int n, cntCore;
int ans, maxCore;
int dx[4]={-1,0,0,1};
int dy[4]={0,-1,1,0};
int go(int cores, int h){
int len=0;
int tempX= core[cores][0]+dx[h];
int tempY= core[cores][1]+dy[h];
while( tempX>=0 && tempX<n && tempY>=0 && tempY<n){
map[tempX][tempY]=1-map[tempX][tempY];
len++;
tempX+=dx[h];
tempY+=dy[h];
}
return len;
}

bool check(int cores , int h){
int tempX= core[cores][0]+dx[h];
int tempY= core[cores][1]+dy[h];
while( tempX>=0 && tempX<n && tempY>=0 && tempY<n){
if(map[tempX][tempY]==1) return false;
tempX+=dx[h];
tempY+=dy[h];
}
return true;
}

void Try(int tempCore, int coreNum, int wireLen){
if(tempCore==cntCore){
if(coreNum>maxCore){
maxCore = coreNum;
ans=wireLen;}
else if( coreNum == maxCore && wireLen<ans) ans=wireLen;
return ;
}
bool flag= true;
for(int h=0; h<4; h++){
if(check(tempCore,h)){
flag=false;
int len=go(tempCore,h);
Try(tempCore+1,coreNum+1,wireLen+len);
go(tempCore,h);
}

}
if(flag) Try(tempCore+1, coreNum,wireLen);
}

int main(int argc, char** argv)
{
int test_case;
int T;

freopen("text.txt", "r", stdin);
cin >> T;
for(test_case = 1; test_case <= T; ++test_case)
{
cin>>n;
cntCore=0;
for(int i=0; i<n;i++){
for(int j=0 ; j<n; j++){
cin>>map[i][j];
if(map[i][j]==1){
core[cntCore][0]=i;
core[cntCore][1]=j;
cntCore++;
}

}

}
maxCore=0;
ans=100000;
Try(0,0,0);

cout << "#" << test_case << " " << ans << endl;
}
return 0;//Your program should return 0 on normal termination.
}```