Untitled

===quangcao===

#include <iostream>
#define _CRT_SECURE_NO_WARNINGS
using namespace std;

/*
Tư tưởng là:
Tìm khoảng thời gian (bắt đầu có khách - khách cuối cùng rời khỏi)
Băm khoảng này thành các slots thời gian
Có 3 quảng cáo. Try từ quảng cáo 1
Mỗi quảng cáo có n khe lựa chọn
Cứ gắn quảng cáo vào rồi check. Khi gắn đủ 3 quảng cáo thì tìm điểm lớn nhất
*/


int N; // số khách hàng
int L[4]; // thời gian của mỗi quảng cáo
int P[4]; // điểm thưởng cho mỗi quảng cáo
int minT; // thời gian có khách hàng đầu tiên
int maxT; // thời gian có khách hàng cuối cùng 
int adv[4][2]; // quảng cáo thời gian bắt đầu và thời gian kết thúc
int V[51][2]; // khách hàng truy cập và thời gian bắt đầu và kết thúc
int ans;

void reset() { // reset thời gian vào và thời gian kết thúc của quảng cáo
	for (int i = 1; i <= 3; i++)
		adv[i][0] = adv[i][1] = 0;
}
int TinhDiem() {
	int point = 0;
	for (int i = 1; i <= N; i++) {
		int maxP = 0;
		for (int j = 1; j <= 3; j++) {
			if (adv[j][0] >= V[i][0] && adv[j][1] <= V[i][1])
				if (P[j] > maxP)
					maxP = P[j];
		}
		point += maxP;
	}
	return point;
}

int check(int k, int st_slot) {
	for (int i = 1; i < k; i++) {
		int ed_slot = st_slot + L[k]-1;

		if (adv[i][0] <= st_slot && st_slot <= adv[i][1]) return 0; // đã có quảng cáo chứa st_slot
		if (adv[i][0] <= ed_slot && ed_slot <= adv[i][1]) return 0; // đã có quảng cáo chứa ed_slot
		if (st_slot <= adv[i][0] && adv[i][0] <= ed_slot) return 0; // khoảng slot chứa điểm đầu quảng cáo khác
		if (st_slot <= adv[i][1] && adv[i][1] <= ed_slot) return 0; // khoảng slot chứa điểm cuối quảng cáo khác
	}
	return 1; // nếu là quảng cáo đàu tiên thì chắc chắn vứt vào được
}

void set(int k, int st_slot) { // điềm thời gian bắt đầu và kết thúc của quảng cáo
	adv[k][0] = st_slot;
	adv[k][1] = st_slot + L[k]-1;
}

void unset(int k, int st_slot) { // bỏ thời gian bắt đầu và kết thúc của quảng cáo
	adv[k][0] = adv[k][1] = 0;
}


void backTrack(int k) {
	if (k == 4) { // hết 3 quảng cáo thì tính điểm
		int point = TinhDiem();
		if (point > ans)
			ans = point; // trả về điểm lớn nhất và thoát
		return;
	}

	for (int i = minT; i <= maxT+1; i++) {
		if (check(k, i)) {
			set(k, i);
			backTrack(k + 1);
			unset(k, i);

		}
	}
}


int main() {
	freopen("input.txt", "r", stdin);
	int T;
	cin >> T;
	for (int tc = 1; tc <= T; tc++) {
		cin >> N; //  Nhập vào số khách hàng
		cin >> L[1] >> L[2] >> L[3];
		cin >> P[1] >> P[2] >> P[3];

		minT = 100; maxT = -1;
		int a, d;
		for (int i = 1; i <= N; i++) {
			cin >> a >> d;
			V[i][0] = a;
			V[i][1] = a + d-1;

			if (V[i][1] > maxT) maxT = V[i][1];
			if (V[i][0] < minT) minT = V[i][0];
		}
		reset();
		ans = 0;
		backTrack(1);
		cout << "Case #" << tc << endl << ans << endl;
	}
	return 0;
}

=====chip====
#include<iostream>
using namespace std;
// code 100/100

int tc,n;
int map[12][12], visited[12][12];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int chip[12][2], Minn=987654,TongChip=0,dai=0;

bool checkMap(int x, int y){
	return (0<=x && x<n && 0<=y && y<n);
}

bool checkHuong (int x, int y, int hgx, int hgy){
	int nx = x+hgx;
	int ny = y+hgy;
	while(checkMap(nx,ny)){
		if(visited[nx][ny]==1){
			return false;
		}
		nx += hgx;
		ny += hgy;
	}
	return true;
}
void visit(int x, int y, int hgx, int hgy, int val){
	int nx = x+hgx;
	int ny = y+hgy;
	dai=0;
	while(checkMap(nx,ny) && map[nx][ny]==0){
		dai++;
		visited[nx][ny]+=val; // đánh dấu ô đã đi qua
		nx += hgx;
		ny += hgy;
	}
}
void BT(int ch,int sum){ // chip, sum
	if(sum>Minn) return;
	if(ch==TongChip){
		if(sum<Minn) Minn=sum;
		return;
	}
	int x=chip[ch][0];
	int y=chip[ch][1];
	if(x==-1 && y==-1){ // chip(-1,-1) là ko thể nối nguồn
		BT(ch+1,sum);
	}
	else{
		for(int i=0;i<4;i++){
			if(checkHuong(x,y,dx[i],dy[i]) ){
				visit(x,y,dx[i],dy[i],1);
				BT(ch+1,sum+dai);
				visit(x,y,dx[i],dy[i],-1); // trả lại visit
			}
		}
		return;
	}
}
int main(){
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	cin>>tc;
	for(int t=1;t<=tc;t++){
		cin>>n;
		Minn=987654;
		TongChip=0;
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				visited[i][j]=0;
				cin>>map[i][j];
				if(map[i][j]==1){
					visited[i][j]=1;
					if(1<=i && i <= n-1 && 1<=j && j <= n-1){ // chỉ lưu các chip trong bo
						chip[TongChip][0]=i;
						chip[TongChip][1]=j;
						TongChip++;
					}
				}
			}
		}
		for(int i=0;i<TongChip;i++){ // check tất cả các chip
			bool ch[4];
			for(int j=0;j<4;j++){
				ch[j]=checkHuong(chip[i][0],chip[i][1],dx[j],dy[j]);
			}
			if(!ch[0] && !ch[1] && !ch[2] && !ch[3] ){ // chip ko đi được hướng nào cả
				chip[i][0]=-1;
				chip[i][1]=-1;
			}
		}
		BT(0,0);
		cout<<"#"<<t<<" "<<Minn<<endl;
	}
	return 0;
}

==========domino===========
#include <iostream> 
using namespace std;
// code 100/100
int map[7][8];
int domino[7][7];
int visit[7][8];
int ans;
int dx[2] = {1,0};
int dy[2] = {0,1};
void Try(int k){
    if (k == 56){
        ans++;
        return;
    }
    int x = k / 8;
    int y = k % 8;
    if (!visit[x][y]){
        for (int d = 0; d < 2; d++){
            int xx = x + dx[d];
            int yy = y + dy[d];
            if (xx>=0 && xx <7 && yy>=0 && yy<8 && !visit[xx][yy] && !domino[map[x][y]][map[xx][yy]]){
                visit[x][y] = visit[xx][yy] = 1;
                domino[map[x][y]][map[xx][yy]] = domino[map[xx][yy]][map[x][y]] = 1;
                Try (k+1);
                visit[x][y] = visit[xx][yy] = 0;
                domino[map[x][y]][map[xx][yy]] = domino[map[xx][yy]][map[x][y]] = 0;
            }
        }
    }
    else Try(k+1);
}
int main(){
	freopen("input.txt", "r", stdin);
    int T;
    cin >> T;
    for (int tC = 1; tC <= T; tC++){
        for (int i = 0; i < 7; i++)
            for (int j = 0; j < 8; j++){
                cin >> map[i][j];
                visit[i][j] = 0;
            }
        for (int i = 0; i < 7; i++)
            for (int j = 0; j < 7; j++)
                domino[i][j] = 0;
        ans = 0;
        Try(0);
        cout << "#" << tC << " " << ans << endl;
    }
    return 0;
}


======cắt giấy=====
#include<iostream>

// code mentor ngắn gọn, tối ưu hơn

using namespace std;
int a[129][129] ={0};
int N,W,B;
int checkMau(int hang, int cot, int n)
{
	for(int i = 0; i< n; i++)
		for(int j = 0; j<n; j++)
			if(a[hang+i][cot+j] != a[hang][cot])
				return 2;
	return a[hang][cot];
}
void cat(int hang, int cot, int n)
{
	
	int st = checkMau(hang,cot,n);
	if(st==2)
	{
		cat(hang,cot,n/2);
		cat(hang,cot+n/2,n/2);
		cat(hang+n/2,cot,n/2);
		cat(hang+n/2,cot+n/2,n/2);
	}
	else
	{
		if(st==0) W++;
		else B++;
	}
}
void

int main()
{
	int T;
	//freopen("input.txt","r",stdin);
	cin >> T;
	for(int tc = 1; tc <= T; tc++)
	{
		cin >> N;
		for(int i = 0; i< N; i++)
			for(int j = 0; j< N; j++)
				cin>>a[i][j] ;
		W=0;B=0;
		cat(0,0,N);
		cout <<"Case #"<< tc<< endl<<W<<" "<< B<<endl;
	}
	return 0;
}

=====đào vàng=======
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;

int N; // kích thước map 
int G; // số lượng mỏ vàng
int arr[21][21];
int arrGold[5][3]; //lưu tọa độ Vàng
int tempArrGold[5][3];
int Q[200][3];
int front, rear;
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};
int visited[21][21];
int cntMin;
int maxCntGold;


int bfs(int i, int j){
	front = rear = 0;

	int cntGold = 0;
	int cntStep = -1;

	Q[rear][0] = i;
	Q[rear][1] = j;
	Q[rear++][2] = 0;
	visited[i][j] = 1;
	while(front < rear){
		int x = Q[front][0];
		int y = Q[front][1];
		int cnt = Q[front++][2];
		for (int dir = 0; dir < 4; dir++)
		{
			int nx = x + dx[dir];
			int ny = y + dy[dir];
			if(nx >= 1 && nx <= N && ny >= 1 && ny <= N && visited[nx][ny] == 0 && arr[nx][ny] != 0){
				Q[rear][0] = nx;
				Q[rear][1] = ny;
				Q[rear++][2] = cnt+1;
				visited[nx][ny] = 1;
				if(arr[x][y] == 2){ // nếu là mỏ vàng
					cntGold++;
					for (int i = 1; i <= G; i++){
						if(x == arrGold[i][0] && y == arrGold[i][1]){
							tempArrGold[i][2] = 1; //đánh dấu mỏ vàng đã được thăm
						}
					}

					if(maxCntGold < cntGold){
						maxCntGold = cntGold;
						cntMin = 999999;
					}
					if(cntGold == maxCntGold && cnt+1 < cntMin){
						for (int i = 1; i <= G; i++){
							arrGold[i][2] = tempArrGold[i][2];
						}
						cntStep = cnt+1;
					}
				}

			}
		}
	}
	return cntStep;
}

void clear_vs(){ // xóa mảng thăm
	for (int i = 1; i <= N; i++){
		for (int j = 1; j <= N; j++){
			visited[i][j] = 0;
		}
	}
}

void check_arr(){
	for (int i = 1; i <= N; i++){
		for (int j = 1; j <= N; j++){
			if(arr[i][j] == 1){
				for (int ki = 1; ki <= G; ki++){
					tempArrGold[ki][2] = 0;
				}
				clear_vs();
				int c = bfs(i, j);
				if(c != -1 && c < cntMin) cntMin = c;
			}
		}
	}
}

int main(){
	int tc;
	int T;
	int Answer;
	int R, C;

	freopen("input.txt", "r", stdin);
	cin >> T;

	for(tc = 1; tc <= T; ++tc){
		Answer = 0;
		cin >> N >> G;
		for (int i = 1; i <= G; i++)
		{
			cin >> R >> C;
			tempArrGold[i][0] = arrGold[i][0] = R;
			tempArrGold[i][1] = arrGold[i][1] = C;
			tempArrGold[i][2] = arrGold[i][2] = 0;
		}
		for (int i = 1; i <= N; i++){
			for (int j = 1; j <= N; j++){
				cin >> arr[i][j];
			}
		}
		for (int i = 1; i <= G; i++)
		{
			arr[arrGold[i][0]][arrGold[i][1]] = 2; // gán tọa độ mỏ vàng bằng 2
		}
		cntMin = 999999;
		maxCntGold = 0;
		check_arr();
		if(cntMin == 999999) cntMin = -1;
		cout << "Case #" << tc << endl << cntMin << endl;

		if(cntMin!=-1 && maxCntGold != K)
			for (int i = 0; i < K; i++)
			{
				if(arrGold[i][2] == 0){
					cout << arrGold[i][0]+1 << " " << arrGold[i][1]+1 << endl;
				}
			}
	}
	return 0;
}

======ong nâu====
#include<iostream>
using namespace std;
//#define _CRT_SECURE_NO_WARNINGS
int n, m;
int a[35][35];
int visit[36][36];
int Ans;
int dx[] = { 1,-1,-1,0,2,-2};
int dy[] = { -1,-1,1,1,0,0};
bool check(int x, int y) {
	if (x > 0 && x <= m && y > 0 && y <= n)return true;
	return false;
}
void reset() {
	for (int i = 1; i <= 35; i++){
		for (int j = 1; j <= 35; j++){
			visit[i][j] = 0;
		}
	}
}
void Try(int x, int y, int cnt, int sum) {
	if (cnt == 4) {
		if (sum > Ans) Ans = sum;
		return;
	}
	for (int i = 0; i < 6; i++){
		int tx = x + dx[i];
		int ty = y + dy[i];
		if (check(tx, ty) && visit[tx][ty] == 0 && a[tx][ty] != 0) {
			visit[tx][ty] = 1;
			Try(tx, ty, cnt + 1, sum + a[tx][ty]);
			Try(x, y, cnt + 1, sum + a[tx][ty]);
			visit[tx][ty] = 0;
		}
	}
}

int main() {
	int T;
	freopen("input.txt", "r", stdin);
	cin >> T;
	for (int tc = 1; tc <= T; tc++) {
		cin >> n >> m;
		m = m * 2;
		for (int i = 1; i <= m; i = i + 2) {
			for (int j = 1; j <= n; j++) {
				if (j % 2 == 1) {
					cin >> a[i][j];
					visit[i][j] = 0;
				}
				else {
					cin >> a[i + 1][j];
					visit[i + 1][j] = 0;
				}
			}
		}
		reset();
		Ans = 0;
		for (int i = 1; i <= m; i++){
			for (int j = 1; j <= n; j++){
				if (a[i][j] != 0) {
					visit[i][j] = 1;
					Try(i, j, 1, a[i][j]);
					visit[i][j] = 0;
				}
			}
		}
		cout << "Case #" << tc << " " << Ans*Ans << endl;
	}
	return 0;
}


=====khu rừng====
#include<conio.h>
#include<iostream>

//CODE 100/100
using namespace std;

int tc, M,N,visited_chay[16][16], kimcuong[16][16], VS_hugo[16][16], KC[16][16];
int ans, cnt, damchay, ho, thoat;
int mt[16][16];  // 0:dat, 1:damchay, 2:ho, 3:loi thoat, 4:vitri ban dau hugo
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
int QX[100001], QY[100001], front, rear;
int loithoat[16][16];

void init(){
	for(int i=1;i<=15;i++){
		for(int j=1;j<=15;j++){
			mt[i][j]=visited_chay[i][j]=kimcuong[i][j]=VS_hugo[i][j]=KC[i][j]=loithoat[i][j]=0;
		}
	}
}

bool isSafe(int x, int y){
	if(x>0 && x<=M && y>0 && y<=N) return true;
	else return false;
}

void bfs_chay(){
	front=rear=0;
	for(int i=1;i<=M;i++){
		for(int j=1;j<=N;j++){
			if(mt[i][j]==1){
				QX[rear]=i; 
				QY[rear++]=j;
				visited_chay[i][j]=1;
			}
		}
	}	
	while(front!=rear){
		int x=QX[front]; 
		int y=QY[front++];
		for(int z=0;z<4;z++){
			int nx=x+dx[z]; 
			int ny=y+dy[z];
			if(isSafe(nx,ny) && visited_chay[nx][ny]==0 && mt[nx][ny]==0){
				QX[rear]=nx; 
				QY[rear++]=ny;
				visited_chay[nx][ny]=visited_chay[x][y]+1;
			}
		}
	}
	for(int i=1;i<=15;i++){
		for(int j=1;j<=15;j++){
			if (visited_chay[i][j] == 0)
				visited_chay[i][j] = 10000;
		}
	}
}

int tong;
void bt(int x, int y, int cnt){
	if(loithoat[x][y]==3){
		if(ans<tong) ans=tong;
	}
	for(int z=0;z<4;z++){
		int nx=x+dx[z];
		int ny=y+dy[z];
		if(isSafe(nx,ny) && VS_hugo[nx][ny]==0 && ((cnt+1)<visited_chay[nx][ny])){
			VS_hugo[nx][ny]=1;
			tong+=kimcuong[nx][ny];
			int t  = mt[nx][ny]==0?1:2;
			bt(nx,ny,cnt+t);
			VS_hugo[nx][ny]=0;
			tong-=kimcuong[nx][ny];
		}
	}
}
int main(){
	freopen("input.txt","r",stdin);
	cin>>tc;
	for(int t=1;t<=tc;t++){
		int x_st, y_st;
		init();
		cin>>M>>N>>x_st>>y_st;
		cin>>damchay;
		for(int i=0;i<damchay;i++){
			int a, b;
			cin>>a>>b;
			mt[a][b]=1;
		}
		cin>>ho;
		for(int i=0;i<ho;i++){
			int a,b;
			cin>>a>>b;
			mt[a][b]=2;
			visited_chay[a][b]=1000;
		}
		cin>>thoat;
		for(int i=0;i<thoat;i++){
			int a, b;
			cin>>a>>b;
			loithoat[a][b]=3;
		}
		for(int i=1;i<=M;i++){
			for(int j=1;j<=N;j++){
				cin>>kimcuong[i][j];
			}
		}	
		bfs_chay();
		ans=-1;
		tong=kimcuong[x_st][y_st];
		VS_hugo[x_st][y_st]=1;
		bt(x_st,y_st,1);
		cout<<"Case #"<<t<<endl;
		if(ans==-1) cout<<-1<<endl;
		else cout<<ans<<endl;
	}
	getch();
	return 0;
}

=====Climb=====
#include<iostream>
// code 100/100
using namespace std;
int N, M;
int arr[51][51];
int visited[51][51];
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};
int xStart, yStart; //Tọa độ Mario
int xEnd, yEnd; // Tọa độ vàng
bool check = false;
int QX[1000001];
int QY[1000001]; // mảng lưu tọa độ
int front, rear;
void clear_visit(){
	for (int i = 1; i <= N; i++){
		for (int j = 1; j <= M; j++){
			visited[i][j] = 0;
		}
	}
}

bool isSafe(int x, int y){
	if(0<x && x<=N && 0<y && y<=M) return true;
	else return false;
}

void bfs(int row, int col, int step){
	front = rear = 0;
	QX[rear] = row;
	QY[rear++] = col;
	visited[row][col] = 1;
	while(front != rear){
		int x = QX[front]; // đi từ front
		int y = QY[front++];
		for (int st = 1; st <= step; st++){ // có thể nhảy st bước, tối đa step bước
			for (int i = 0; i < 4; i++){ // đi 4 hướng
				int nx = x + dx[i]*st;
				int ny = y + dy[i];
				if(isSafe(nx,ny) && visited[nx][ny] == 0 && arr[nx][ny] != 0){ // là ô 1 và chưa thăm 
					QX[rear] = nx; // ok thì nhét vào rear
					QY[rear++] = ny;
					visited[nx][ny] = 1;
					if(visited[xEnd][yEnd] == 1){ // tới khi tìm được vàng thì check = true rồi break
						check = true;
						break; // tìm thấy vàng là break
					}
				}
			}
			if(check) break; // chỉ cần có hướng đi là break
		}
		if(check) break; // chỉ cần có bước nhảy tối thiểu là break
	}
}

int main(){
	int tc;
	int T;
	int Answer;
	freopen("input.txt", "r", stdin);
	cin >> T;

	for(tc = 1; tc <= T; ++tc){
		cin >> N >> M;
		check = false;
		for (int i = 1; i <= N; i++){
			for (int j = 1; j <=M; j++){
				cin >> arr[i][j];
				if(arr[i][j] == 2){
					xStart = i;
					yStart = j;
				}
				if(arr[i][j] == 3){
					xEnd = i;
					yEnd = j;
				}
			}
		}
		int step = 1;
		while(!check){
			clear_visit();
			bfs(xStart, yStart, step); // bfs từ vị trí đầu tiên
			if(check){
				break;
			}
			step++;
		}
		cout << "Case #" << tc << endl << step << endl;
	}
	return 0;
}
======nước biển====
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
// code 100/100
int N, M;
int arr[101][101];
int visited[101][101];
int Q[10002][2];
int Qsea[10002][2];
int frontb, rearb;
int cntArea;
int front, rear;

int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};
int mucnuoc;
int cntVisit;
using namespace std;

void bfs_cnt_area(){
	for (int i = 0; i < N; i++){
		for (int j = 0; j < M; j++){
			front = rear = 0;
			if(visited[i][j] == 0){
				cntVisit++;
				Q[rear][0] = i;
				Q[rear++][1] = j;
				visited[i][j] = 1;
				while(front != rear){
					int row = Q[front][0];
					int col = Q[front++][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 < M && visited[x][y] == 0){
							cntVisit++;
							visited[x][y] = 1;
							Q[rear][0] = x;
							Q[rear++][1] = y;
						}
					}
				}
				if(rear != 0 && cntVisit < N*M)
					return;
			}
		}
	}
	return;
}

void loang_bien(){
	while(rearb != frontb){
		int row = Qsea[frontb][0];
		int col = Qsea[frontb++][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 < M && arr[x][y] <= mucnuoc && visited[x][y] == 0){
				visited[x][y] = 1;
				Qsea[rearb][0] = x;
				Qsea[rearb++][1] = y;
				cntVisit++;
			}
		}
	}
}

void clear(){
	for (int i = 0; i < N; i++){
		for (int j = 0; j < M; j++){
			visited[i][j] = 0;
		}
	}
}

int main(){
	int test_case = 0;
	int T;
	int Answer;

	freopen("input.txt", "r", stdin);

	while(true){
		cin >> N >> M;
		if(N != 0 && M != 0){
			test_case++;
			for (int i = 0; i < N; i++){
				for (int j = 0; j < M; j++){
					cin >> arr[i][j];
					visited[i][j] = 0;
				}
			}
			mucnuoc = 0;
			while(mucnuoc < 1001){
				frontb = rearb = 0;
				clear();
				cntVisit = 0;
				for (int i = 0; i < N; i++){
					if(arr[i][0] <= mucnuoc ){
						visited[i][0] = 1;
						Qsea[rearb][0] = i;
						Qsea[rearb++][1] = 0;
						cntVisit++;
						//break;
					}
					if(arr[i][M-1] <= mucnuoc){
						visited[i][M-1] = 1;
						Qsea[rearb][0] = i;
						Qsea[rearb++][1] = M-1;
						cntVisit++;
					}
				}
				for (int i = 1; i < M-1; i++){
					if(arr[0][i] <= mucnuoc ){
						visited[0][i] = 1;
						Qsea[rearb][0] = 0;
						Qsea[rearb++][1] = i;
						cntVisit++;
						//break;
					}
					if(arr[N-1][i] <= mucnuoc){
						visited[N-1][i] = 1;
						Qsea[rearb][0] = N-1;
						Qsea[rearb++][1] = i;
						cntVisit++;
					}
				}
				if(rearb != 0){
					loang_bien();
					bfs_cnt_area();
					if(cntVisit < N*M){
						break;
					}
				}
				mucnuoc++;
			}
			if(cntVisit == N*M)
				cout << "Case " << test_case << ": " << "Island never splits." << endl;
			else cout << "Case " << test_case << ": " << "Island splits when ocean rises " << mucnuoc << " feet." << endl;
		}
		if(N==0 && M == 0) break;
	}
	return 0;
}
=====ống nước===
#include<iostream>
using namespace std;
int N, M;
int P; // giới hạn bơm
// mảng 8 loại đường ống
int DuongOng[8][4]={
	0,0,0,0,
	1,1,1,1,
	1,0,1,0,
	0,1,0,1,
	1,1,0,0,
	0,1,1,0,
	0,0,1,1,
	1,0,0,1 };

int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};

int visit[51][51]; // mảng thăm
int cntN[51][51]; // mảng lan truyền
int map[51][51]; // mang đường ống
int Qx[10000];
int Qy[10000];
int rear, front;
int cnt; //đếm số đường ống 

bool check(int x, int y){
	if(x >= 0 && x < N && y >= 0 && y < M)return true;
	return false;
}
void BFS(int x_mb, int y_mb){
	front = rear = 0;
	Qx[rear] = x_mb;
	Qy[rear++] = y_mb;
	visit[x_mb][y_mb] = 1;
	cntN[x_mb][y_mb] = 1;
	while (front < rear){
		int x = Qx[front];
		int y = Qy[front++];
		for (int i = 0; i < 4; i++){
			int nx = x + dx[i]; // vị trí sắp đi đến
			int ny = y + dy[i];
			if(check(nx, ny)) // check vị trí sắp đi đến
			{
				if(map[nx][ny] != 0 && visit[nx][ny] == 0 && DuongOng[map[x][y]][i] == 1 && DuongOng[map[nx][ny]][(i+2)%4] == 1)
				{ // nếu vị trí sắp tới khác 0, chưa thăm, đầu của 2 loại ống phù hợp nhau
					cntN[nx][ny] = cntN[x][y] + 1; // lan truyền giới hạn bơm 
					if(cntN[nx][ny] > P)return;
					cnt++;
					Qx[rear] = nx;
					Qy[rear++] = ny;
					visit[nx][ny] = 1;
				}
			}
		}
	}
}
void reset(){
	for (int i = 0; i <= N; i++){
		for (int j = 0; j <= M; j++){
			visit[i][j] = 0;
			cntN[i][j] = 0;
		}
	}
}

int main(){
	int T;
	int x_mb,y_mb;
	freopen("input.txt", "r", stdin);
	cin>>T;
	for (int tc = 1; tc <= T; tc++)
	{
		cnt = 1;
		cin>>N>>M>>x_mb>>y_mb>>P;
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < M; j++)
			{
				cin>>map[i][j];
			}
		}
		reset();
		BFS(x_mb,y_mb);
		cout<<"Case #"<<tc<<endl;
		cout<<cnt<<endl;
	}
	return 0;
}

====skyforce===
#include<iostream>
#include<conio.h>

// chưa hiểu lắm

using namespace std;
int N;
int map[15][5];
// màn hình chơi game chỉ có 5*5
int mapcop[5][5];
int ans;
int dx[] = {-1,-1,-1}; // trái, giữa, phải
int dy[] = {-1, 0, 1};
void reset(){
   // mảng cố định và mảng 5*5
	for (int i = 0; i < N; i++){
			for ( int j = 0; j < 5; j++){
			   map[i][j] = 0;
			}
	}
	for (int i = 0; i < 5; i++){
			for ( int j = 0; j < 5; j++){
				mapcop[i][j] = 0;
			}
	}
}
void backtrack(int x, int y, int sum){
	// lên đỉnh
	if(x == 0){
	  if(ans < sum) ans = sum;
	  return;
	}
	// đi 3 hướng
	for(int i = 0; i < 3; i++){
	  int tempx = x + dx[i];
	  int tempy = y + dy[i];
	  if(tempx >= 0 && tempx < N && tempy >= 0 && tempy < 5){
		  backtrack(tempx,tempy, sum + map[tempx][tempy]);
	  }
	}
}

void No_map(int x){
	// tính từ vị trí dùng
       for (int i = x; i < 5+x; i++){
			for ( int j = 0; j < 5; j++){
		        mapcop[i-x][j] = map[i][j]; // copy mảng trước khi nổ
				// cho nổ hết các giá trị  -1(hay chính là 2)
				if(map[i][j] == -1){
				   map[i][j] = 0;
				}
			}
		}
}
/// trả lại giá trị vào mảng 
void Push_map(int x){
	for(int i = x; i < 5+x; i++){
		for(int j = 0; j < 5; j++){
			map[i][j] = mapcop[i-x][j]; // gán lại mảng sau mỗi lần nổ xong
		}
	}
}
int main(){
	freopen("input.txt","r",stdin);
	int TC; cin >> TC;
	for (int tc = 1; tc <= TC; tc++){
		reset();
		cin >> N;
		for (int i = 0; i < N; i++){
			for ( int j = 0; j < 5; j++){
			  cin >> map[i][j];
			  if(map[i][j] == 2){
			     map[i][j] = -1;
			  }
			  }
			}
		ans = -1;
		for(int i = 0; i <= N-5; i++){
			No_map(i); // nổ map
			backtrack(N,2,0);
			Push_map(i); // gán lại map cho bước di chuyển mới
		}
		cout << "Case #" << tc << endl;
		cout << ans << endl;
		}
	getch();
	return 0;
}
====tấn công===

#include<iostream>
using namespace std;
// mentor 2 100
int const max_size = 105;
int const vc = 1000000;
int mayBD[max_size];
int A[max_size][max_size];
int visit[max_size];
int n;           // Số Thành
int ans;
bool flag;        // Tìm được chu trình hay không
void reset(){                // Reset de dfs
	for( int i = 0; i<n; i++) visit[i] = 0;
}
void dfs(int tempThanh, int thanh, int sl, int tempMin, int d1, int d2){
	if ( tempThanh == thanh && sl >= 3){
		flag = true;
		ans += tempMin;
		A[d1][d2] = 0;
		A[d2][d1] = 0;
		return;
	}
	for(int col =0; col< n; col++){
		if (flag)  return;
		if (A[tempThanh][col] == 1 && (!visit[col] || (col == thanh && sl >= 3))){
			visit[col] = 1;
			int value = mayBD[tempThanh] + mayBD[col];
			if( tempMin > value) {
				dfs(col,thanh,sl+1,value, tempThanh, col);
			} else{
				dfs(col,thanh,sl+1,tempMin,d1,d2);
			}
		}
	}
}
void solve(){
	for(int thanh = 0; thanh <n; thanh++){        // Duyệt các thành để dfs
		reset();
		visit[thanh] = 1;
		flag = false;
		dfs(thanh, thanh, 1, vc, -1, -1);
		while(flag){
			reset();
			visit[thanh] = 1;
			flag = false;
			dfs(thanh, thanh, 1, vc, -1, -1);
		}
	}
}
int main(){
	freopen("input1.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<n; j++){
				A[i][j] = 0;                // Reset matran
			}
		}
		int thanh, soMayBD,slKe, tempThanh;
		for (int i = 0; i<n; i++) {
			cin>>thanh>>soMayBD>>slKe;
			mayBD[thanh] = soMayBD;
			for(int k = 0; k< slKe; k++){
				cin>>tempThanh;
				A[thanh][tempThanh] = 1;
				A[tempThanh][thanh] = 1;
			}
		}
		ans = 0;
		solve();
		cout<<ans<<endl;
	}
	return 0;
}

===thống trị khu vực s6===

#include<iostream>
using namespace std;
// code 100/100
int map[105][105];
int mapCopy[105][105];
int visit[105][105];
int Que[10000][2];
int n, ans, T;
int TS[6]; // mảng lưu tần số xuất hiện của các số
int dx[] = { 0, -1, 0, 1 };
int dy[] = { -1,0, 1,0 };
void reset() {
	for (int i = 0; i < 6; i++)  TS[i] = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) visit[i][j] = 0;
	}
}
void dfs(int x, int y, int oVal, int nVal) {           // Tô màu cho cửa hàng
	for (int h = 0; h < 4; h++) {
		int nx = x + dx[h];
		int ny = y + dy[h];
		if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
		if (!visit[nx][ny] && mapCopy[nx][ny] == oVal) {
			visit[nx][ny] = 1;
			mapCopy[nx][ny] = nVal;
			dfs(nx, ny, oVal, nVal);
		}
	}
}
void bfs(int x, int y) {
	reset();
	visit[x][y] = 1;
	int front = 0, rear = 0;
	Que[rear][0] = x; // push vị trí đầu vào Queue
	Que[rear++][1] = y;
	while (front < rear) {
		int r = Que[front][0]; // vị trí đang đứng
		int c = Que[front++][1];
		for (int h = 0; h < 4; h++) {
			int nx = r + dx[h]; // vị trí sắp đến
			int ny = c + dy[h];
			if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue; // check vị trí sắp đến
			if (!visit[nx][ny]) { // nếu vị trí sắp tới chưa được thăm
				if ((map[r][c] == 0) || (map[nx][ny] == map[r][c])) {
					TS[map[nx][ny]] ++;                    // Tăng tần số xuất hiện cho số đó 
					visit[nx][ny] = 1; // đánh dấu
					Que[rear][0] = nx; // push số đó vào Queue
					Que[rear++][1] = ny;
				}
			}
		}
	}
	int maxTS = TS[1], color = 1;
	for (int i = 2; i <= 5; i++)
		if (TS[i] >= maxTS) {              // Chọn ra số có tần số xuất hiện nhiều nhât
			color = i;
			maxTS = TS[i];
		}
		mapCopy[x][y] = color;
		dfs(x, y, 0, color);
}
void solve() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (mapCopy[i][j] == 0) {
				bfs(i, j);
			}
		}
	}
	reset();
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (!visit[i][j]) {                      // Tìm số vùng
				ans++; 
				visit[i][j] = 1;
				dfs(i, j, mapCopy[i][j], mapCopy[i][j]);
			}
		}
	}
}
int main() {
	freopen("input.txt", "r", stdin);
	cin >> T;
	for (int tc = 1; tc <= T; tc++) {
		cin >> n;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				cin >> map[i][j];
				mapCopy[i][j] = map[i][j];
			}
		}
		ans = 0; solve();
		cout << "Case #" << tc << endl << ans << endl;
	}
	return 0;
}