Untitled

// bai 1 – invite wedding
#include<iostream>
// code 100/100
using namespace std;
int dinh, canh;
int u, v;
int maTranKe[101][101];
int visited[101];
int cntVisit[101];

void dfs(int d){
	if(d == v){
		for (int i = 1; i <= dinh; i++)
		{
			if(visited[i] == 1){
				cntVisit[i]++;
			}
		}
		return;
	}
	
	for (int i = 1; i <= dinh; i++)
	{
		if(visited[i] == 0 && maTranKe[d][i] == 1){
			visited[i] = 1;
			dfs(i);		
			visited[i] = 0;
		}
	}
}

int cnt_dinh(){
	int cnt = 0;
	for (int i = 1; i <= dinh; i++)
	{
		if(cntVisit[i] == cntVisit[v]){
			cnt++;
		}
	}
	return cnt-2;
}

void create(){
	for (int i = 1; i <= dinh; i++)
	{
		for (int j = 1; j <= dinh; j++)
		{
			maTranKe[i][j] = 0;
			
		}
		cntVisit[i] = 0;
		visited[i] = 0;
	}
}
int main(int argc, char** argv)
{
	int test_case;
	int T;
	int Answer;
	int d1, d2;
//	freopen("input.txt", "r", stdin);
	cin >> T;
	for(test_case = 1; test_case <= T; ++test_case)
	{
		Answer = 0;
		cin >> dinh >> canh >> u >> v;
		create();
		for (int i = 0; i < canh; i++)
		{
			cin >> d1 >> d2;
			maTranKe[d1][d2] = 1;
		}
		visited[u] = 1;
		dfs(u);
		Answer = cnt_dinh();
		// Print the answer to standard output(screen).
		cout << Answer << endl << endl;
	}
	return 0;//Your program should return 0 on normal termination.
}

//bai 2 – mario Climb
#include<iostream>

using namespace std;

int N, M;
int map[55][55];
int visit[55][55];

int ans;

int dR[4] = {0, -1, 0, 1};
int dC[4] = {-1, 0, 1, 0};

struct COOR {
	int r, c;
} Queue[2505];

int front, rear;

void init() {
	front = rear = -1;

	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			visit[i][j] = 0;
}

void push(int r, int c) {
	rear++;
	Queue[rear].r = r;
	Queue[rear].c = c;
}

COOR pop() {
	return Queue[++front];
}

bool isEmpty() {
	return front == rear;
}

int BFS(COOR start, COOR end) {
	init();

	visit[start.r][start.c] = 1;
	push(start.r, start.c);

	while (!isEmpty()) {
		COOR coor = pop();

		for (int i = 0; i < 4; i++) {
			int nC = coor.c + dC[i];
			for (int j = 1; j <= ans; j++) {
				int nR = coor.r;
				if (dR[i] != 0)
					nR += (j * dR[i]);

				if (nR >= 0 && nR < N && nC >= 0 && nC < M && !visit[nR][nC] && map[nR][nC]) {
					if (nR == end.r && nC == end.c) {
						return 1;
					}

					visit[nR][nC] = 1;
					push(nR, nC);
				}
			}
		}
	}

	return 0;
}

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

	for (int test_case = 1; test_case <= T; ++test_case) {
		cin >> N >> M;

		COOR start, end;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				cin >> map[i][j];
				if (map[i][j] == 2) {
					start.r = i; start.c = j;
				}

				if (map[i][j] == 3) {
					end.r = i; end.c = j;
				}
			}
		}

		ans = 1;

		while (!BFS(start, end)) {
			ans++;
		}

		cout << "Case #" << test_case << endl << ans << endl;
	}
	return 0;
}
/// bai 3: dominating area
#include<iostream>
using namespace std;
int N;
int arr[101][101];
int tempArr[101][101];
int Q[1000000][3];
int front, rear;
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};
int visited[101][101];
int cntArr[6];
int cntArea;



void clear_queue(){
	front = rear = 0;
}
void clear_arr(){
	for (int i = 0; i < 6; i++)
	{
		cntArr[i] = 0;
	}
}
void clear_visited(){
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			visited[i][j] = 0;
		}
	}
}
void clear(){
	clear_arr();
	clear_queue();
	clear_visited();
}
void start_queue(int row, int col){
	front = rear = 0;
	Q[rear][0] = 0;
	Q[rear][1] = row;
	Q[rear++][2] = col;
	visited[row][col] = 1;
}
void start_area(){
	//int temp = 0;
	while(front != rear){
		int value = Q[front][0];
		int row = Q[front][1];
		int col = Q[front++][2];
		for (int i = 0; i < 4; i++)
		{
			int x = row+dx[i];
			int y = col+dy[i];
			if(x < 0 || x >= N || y < 0 || y >= N){
				continue;
			}
			else{
				if(arr[x][y] == 0 && visited[x][y] == 0){
					Q[rear][0] = 0;
					Q[rear][1] = x;
					Q[rear++][2] = y;
					visited[x][y] = 1;
				}
			}
		}
	}
}
void cnt_array(){
	int start = 0;

	for (int i = 0; i < rear; i++)
	{
		cntArr[Q[i][0]]++;
	}
}
void bfs(int row, int col){
	start_queue(row, col);
	start_area();
	front = 0;
	while(front != rear){
		int value = Q[front][0];
		int row = Q[front][1];
		int col = Q[front++][2];
		for (int i = 0; i < 4; i++)
		{
			int x = row+dx[i];
			int y = col+dy[i];
			if(x < 0 || x >= N || y < 0 || y >= N){
				continue;
			}
			else{
				if((value == 0  || (value != 0 && value == arr[x][y])) && visited[x][y] == 0 ){
					Q[rear][0] = arr[x][y];
					Q[rear][1] = x;
					Q[rear++][2] = y;
					visited[x][y] = 1;
				}
			}
		}
	}
	cnt_array();

	int max = 0;
	int index = 0;
	for (int i = 1; i < 6; i++)
	{
		if(cntArr[i] >= max){
			max = cntArr[i];
			index = i;
		}
	}

	int start = 0;
	while (Q[start][0] == 0){
		tempArr[Q[start][1]][Q[start][2]] = index;
		start++;
	}
}

void find(){
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if(arr[i][j] == 0 && visited[i][j] == 0){
				bfs(i, j);
				clear_queue();
				clear_arr();
				clear_visited();
			}
		}
	}
}
void cnt_area(int vtRoot, int vt){
	int row = vt/N;
	int col = vt%N;
	if(vt >= N*N){
		return;
	}
	if(visited[row][col] == 1){
		if(vt==vtRoot){
			cnt_area(vtRoot+1, vt+1);
		}
		return;
	}
	visited[row][col] = 1;
	for (int i = 0; i < 4; i++)
	{
		int x = row+dx[i];
		int y = col+dy[i];
		if(x < 0 || x >= N||y < 0|| y >= N){
			continue;
		}
		else{
			if(tempArr[x][y] == tempArr[row][col] && visited[x][y] == 0){			
				cnt_area(vtRoot, x*N+y);
				//visited[x][y] = 1;
			}
		}
	}
	if(vt == vtRoot){	
		cntArea++;
		cnt_area(vtRoot+1, vt+1);
	}
}
int main(int argc, char** argv)
{
	int test_case;
	int T;
	int Answer;

//	freopen("iput.txt", "r", stdin);
	cin >> T;
	for(test_case = 1; test_case <= T; ++test_case)
	{

		Answer = 0;
		cin >> N;
		clear();
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				cin >> tempArr[i][j];
				arr[i][j] = tempArr[i][j];
			}
		}


		find();
		cntArea = 0;
		cnt_area(0, 0);
		cout << "Case #" << test_case << endl << cntArea << endl;
	}
	return 0;
}

// bai 5 Ads 
#include <iostream>
using namespace std;
struct Visitors
{
	int time_arri, time_dura, v_point; 
}Visitors[51];

struct Advertisement
{
	int time_ad, point;
}QC[5];

struct AD_ST_EN
{
	int st, en;
}AD_ST_EN[5];
int HV[6][3] = {
	{1,2,3},
	{1,3,2},
	{2,1,3},
	{2,3,1},
	{3,1,2},
	{3,2,1} };
int nVistors;
int res;

void Input(){
	cin >> nVistors; 
	for(int i = 1; i <= 3; i++){
		cin >> QC[i].time_ad;
	}
	for(int i = 1; i <= 3; i++){
		cin >> QC[i].point;
	}
	for(int i = 0; i < nVistors; i++){
		cin >> Visitors[i].time_arri >> Visitors[i].time_dura;	
	}
	res = 0;
}


int GetPoint(){
	int tong = 0;
	for(int i = 0; i < nVistors; i++){
		int p_max = 0;
		for(int j = 1; j <=3 ; j++){
			if(Visitors[i].time_arri <= AD_ST_EN[j].st && Visitors[i].time_arri + Visitors[i].time_dura - 1 >= AD_ST_EN[j].en){
				if(QC[j].point > p_max) p_max = QC[j].point;
			}
		}
		tong = tong + p_max;
	}
	return tong;
}

void backtrack(int hv, int idx_ad, int t_next){
	if(idx_ad == 3){
		int s_point = GetPoint();
		if(res < s_point) res = s_point;
		return;
	}
	int ad_ith = HV[hv][idx_ad];
	int ad_time = QC[ad_ith].time_ad;
	int ad_point = QC[ad_ith].point;
	for(int i = t_next; i <= 50 - ad_time; i++){
		if(50 - i >= ad_time){
			AD_ST_EN[ad_ith].st = i;
			AD_ST_EN[ad_ith].en = i + ad_time - 1;
			backtrack(hv, idx_ad + 1, i + ad_time);
			AD_ST_EN[ad_ith].st = 0;
			AD_ST_EN[ad_ith].en = 0;
		}
	}
	backtrack(hv, idx_ad + 1, t_next);
}
int main(){
//	ios::sync_with_stdio(false);
//	cin.tie(NULL);
//	freopen("input.txt", "r", stdin);
	int T; cin >> T;
	for(int tc = 1; tc <= T; tc ++)	{
		Input();

		for(int i = 0; i < 6; i++){
			backtrack(i,0,1);
		}
		cout << "Case #" << tc << endl;
		cout << res << endl;
	}
	return 0;
}