Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
995 B
1
Indexable
Never
#include<iostream>;
using namespace std;
int a[201][201],N;
int dx[3]={-1,-1,-1};
int dy[3]={-1,0,1};
int vang,van,ans;
bool dich;
bool checkbien(int x,int y){
	if(x<1 || x>N ||y<1 || y>5)return false;
}
void backtrack(int x,int y,int k){
	if(k==N+1){
		dich=true;
		if(vang>ans)ans=vang;
		return ;
	}
	for(int i=0;i<3;i++){
		int xx=x+dx[i];
		int yy=y+dy[i];
		if(checkbien(xx,yy)){
			if(a[xx][yy]==2 && van==1){
				van=0;
				backtrack(xx,yy,k+1);
				van=1;
			}
			if(a[xx][yy]==0){
				backtrack(xx,yy,k+1);
			}
			if(a[xx][yy]==1){
				vang+=1;
				backtrack(xx,yy,k+1);
				vang-=1;
			}
		}
	}
}
int main(){
	int T;
	//freopen("Text.txt","r",stdin);
	cin>>T;
	for(int tc=1;tc<=T;tc++){
		cin>>N;
		for(int i=1;i<=N;i++){
			for(int j=1;j<=5;j++){
				cin>>a[i][j];
			}
		}
		ans=0;
		vang=0;
		van=1;
		dich=false;
		backtrack(N+1,3,1);
		cout<<"#"<<tc<<" ";
		if(dich)cout<<ans<<endl;
		else cout<<-1<<endl;
	}
	return 0;
}