Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.0 kB
4
Indexable
Never
#include<iostream>

using namespace std;

int N, K, S;

int Score[25][25];
int ans;

void backTrack(int col, int sum, int lastScore)
{
	if(col == K && sum == S)
	{
		ans++;
	}
	
	if(col == K ||sum >= S)
	{
		return;
	}
	for(int row = 0; row < N; row++)
	{
		if(Score[row][col] >= lastScore )
		{
			backTrack(col + 1, sum + Score[row][col], Score[row][col]);
		}
	}
}


int main()
{
	//freopen("Text.txt","r", stdin);
	int T;
	cin>>T;

	for(int tc =1; tc <= T; tc++)
	{
		cin>>S >> K >> N;

		for(int i = 0; i < N; i++)
		{
			for(int j = 0; j< K; j++)
			{
				cin>>Score[i][j];
			}
		}
		ans = 0;
		backTrack(0,0,0);
		cout<<"Case "<<tc<<endl;

		if(ans != 0)
		{
			cout<<ans<<endl;
		}
		else
		{
			cout<<-1<<endl;
		}
	
	}
	return 0;
}
/////////////////////////////////////////////////////////////
#include <iostream>
using namespace std;
int kq;
int a[30][30];
int c[30];
int used[30][4];
int dem;
int n;
void backtrack(int k){
	if(k==n) {
		dem++;
		return;
	}
	for(int i=0; i<4; i++){
		used[k][i]=0;
	}
	for(int i=0; i<k; i++){
		if(a[k][i]==1) {
			used[k][c[i]]=1;
		}
	}
	for(int i=0; i<4; i++){
		if(used[k][i]==0){
			c[k]=i;
			backtrack(k+1);
		}
	}

}



int main(){
	//freopen("input.txt", "r", stdin);
	//nhap lieu
	int t; 
	cin>>t;
	for(int tc=1; tc<=t; tc++){
		cout<<"Case #"<<tc<<endl;
		cin>>n;
		for(int i=0; i<n; i++){
			for(int j=0; j<n; j++){
				cin>>a[i][j];
			}
		}
		dem=0;
		backtrack(0);
		
		cout<<dem<<endl;
	}
return 0;
}
////////////////////////////////////////////////////////////
3

4

0 0 0 1

0 0 0 1

0 0 0 1

1 1 1 0

5

0 1 1 1 0

1 0 0 1 1

1 0 0 1 0

1 1 1 0 1

0 1 0 1 0

7

0 1 0 0 1 0 1

1 0 1 0 1 0 0

0 1 0 1 1 0 0

0 0 1 0 1 1 0

1 1 1 1 0 1 1

0 0 0 1 1 0 1

1 0 0 0 1 1 0

 


[Sample Output]

Case #1
108

Case #2
96

Case #3
264