Untitled

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;
}