Untitled
unknown
plain_text
2 years ago
2.2 kB
3
Indexable
Connect Processor #include<iostream> using namespace std; int N, cntCore, maxCore; int map[15][15]; int cores[15][2]; int ans; int di[4]={-1, 0, 0, 1}; int dj[4]={0, -1,1, 0}; bool check(int SoCore, int i){ int tempX= cores[SoCore][0] + di[i]; int tempY= cores[SoCore][1] + dj[i]; while(tempX >=0 && tempX < N && tempY >=0 && tempY < N){ //check xem co di day ra toi bien duoc khong if(map[tempX][tempY] ==1) return false; tempX +=di[i]; tempY += dj[i]; } return true; } int chay(int SoCore, int i){ int len = 0; int tempX= cores[SoCore][0] + di[i]; int tempY= cores[SoCore][1] + dj[i]; while(tempX >=0 && tempX < N && tempY >=0 && tempY < N){//check xem co di day ra toi bien duoc khong map[tempX][tempY] =1; len++; tempX +=di[i]; tempY += dj[i]; } return len; } void TraVe(int SoCore,int i){ // Tra ve cac o da noi day thanh 1 ve 0 int tempX= cores[SoCore][0] + di[i]; int tempY= cores[SoCore][1] + dj[i]; while(tempX >=0 && tempX < N && tempY >=0 && tempY < N){ map[tempX][tempY] =0; tempX +=di[i]; tempY += dj[i]; } } void Try(int SoCore, int SoCoreDcNoi, int length){ if(SoCore == cntCore){ if(SoCoreDcNoi > maxCore){ // tim so core dc noi toi da ans = length; maxCore = SoCoreDcNoi; } else if(SoCoreDcNoi == maxCore && length < ans) ans = length; // tim do dai day nho nhat return; } bool CoDiDcKo = false; for(int i=0; i<4; i++){ if(check(SoCore,i)){ CoDiDcKo = true; int len = chay(SoCore, i); Try(SoCore+1, SoCoreDcNoi+1, length +len); TraVe(SoCore, i); } } if(!CoDiDcKo) Try(SoCore+1, SoCoreDcNoi, length); } int main(){ freopen("text.txt", "r", stdin); int T; cin >> T; for(int 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 && i < N-1 && j < N-1){ cores[cntCore][0]=i; cores[cntCore][1]=j; cntCore++; } } } ans =1000000; // chieu dai day toi thieu maxCore =0; // so luong loi toi da Try(0,0,0); cout << "#" << test_case << " " << ans << endl; } return 0; }
Editor is loading...