Untitled
unknown
plain_text
2 years ago
1.9 kB
7
Indexable
// 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. }
Editor is loading...