Untitled

mail@pastecode.io avatar
unknown
plain_text
7 months ago
1.3 kB
9
Indexable
Never
#include <iostream>
using namespace std;
int dy[]={-1,0,1};
int N, Max, cnt, visitBomb, flag;
int Map[13][5];
void backtrack(int k, int col){
	if (k==0){
		if (cnt>Max)
			Max=cnt;
		flag=1;
		return;
	}
	//Dung bom (chua dung thi dung hoac khong dung)
	if (visitBomb==0){
		for (int i=k-1; i>=k-5 && i>=0; i--){
			for (int j=0; j<5; j++){
				if (Map[i][j]==2)
					Map[i][j]=-1;
			}
		}
		visitBomb=1;
		backtrack(k,col);
		for (int i=k-1; i>=k-5 && i>=0; i--){
			for (int j=0; j<5; j++){
				if (Map[i][j]==-1)
					Map[i][j]=2;
			}
		}
		visitBomb=0;
	}
	//Di chuyen
	for (int j=0; j<3; j++){
		int nc=col+dy[j];
		if (nc>=0 && nc<5){
			if (Map[k-1][nc]==0 || Map[k-1][nc]==-1)
				backtrack(k-1,nc);
			else if (Map[k-1][nc]==1){
				cnt++;
				backtrack(k-1,nc);
				cnt--;
			}
			else if (Map[k-1][nc]==2 && cnt>=1){
				cnt--;
				backtrack(k-1,nc);
				cnt++;
			}
		}
	}

}

int main(){
	freopen("input.txt", "r", stdin);
	int T;
	cin>>T;
	for (int tc=1; tc<=T; tc++){
		cin>>N;
		for (int i=0; i<N; i++){
			for (int j=0; j<5; j++){
				cin>>Map[i][j];
			}
		}
		Max=0;
		cnt=0;
		visitBomb=0;
		flag=0;
		backtrack(N,2);
		if (flag==1)
			cout<<"Case #"<<tc<<endl<<Max<<endl;
		else 
			cout<<"Case #"<<tc<<endl<<-1<<endl;
	}

	return 0;
}
Leave a Comment