Untitled

hugo ve nha
	#include <iostream>
	using namespace std;

	int n, res;

	int arr[2][30];
	int soLinh[2][30], soCong;

	void resetLinh(){
		soCong = 0;
		for(int i = 0; i < n; i++){
			soLinh[0][i] = 0;
			soLinh[1][i] = 0;
		}
	}

	int getArmy(){
		int sum = 0;
		for(int i = 0; i < soCong; i++){
			if(soLinh[1][i] < 3) sum += soLinh[0][i];
		}
		return sum;
	}

	void duongVeNha(int cong, int sum){
		if(sum >= res) return;
		if(cong == n){
			if(sum < res) res = sum;
			return;
		}
		duongVeNha(cong+1, sum+arr[1][cong]); // tra tien

		soLinh[0][soCong] = arr[0][cong];
		soLinh[1][soCong] = 0;
		soCong++;
		duongVeNha(cong+1, sum+arr[1][cong]*2);  //mua quan linh
		soLinh[0][soCong] = 0;
		soLinh[1][soCong] = 0;
		soCong--;

		// danh nhau
		int linh = getArmy();
		if(linh >= arr[0][cong]){
			//copy quan Linh
			int quanLinhCopy[2][30];
			for(int i = 0; i < soCong; i++){
				quanLinhCopy[0][i] = soLinh[0][i];
				quanLinhCopy[1][i] = soLinh[1][i];
			}
			//danh nhau
			int linhDich = arr[0][cong];
			for(int i = 0; i < soCong; i++){
				if(soLinh[1][i] < 3){
					if(soLinh[0][i] <= linhDich){
						linhDich -= soLinh[0][i];
						soLinh[0][i] = 0;
					}
					else{
						soLinh[0][i] -= linhDich;
						linhDich = 0;
					}
					soLinh[1][i]++;
				}
			}
			duongVeNha(cong+1, sum);  // backtrack
			for(int i = 0; i < soCong; i++){
				soLinh[0][i] = quanLinhCopy[0][i];
				soLinh[1][i] = quanLinhCopy[1][i];
			}
		}
	}

	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++){
				cin >> arr[0][i] >> arr[1][i];
			}
			resetLinh();
			res = 999999;
			duongVeNha(0, 0);
			cout << "#" << tc << " " << res << endl;
		}
		return 0;
	}

mountantwalking
#include <iostream>
using namespace std;

int n;
int res;
int maxTs, minTs;

int queueX[9999999], queueY[9999999];
int front, rear;

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

int arr[100][100];
int visit[100][100];

void resetVisit(){
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			visit[i][j] = 0;
		}
	}
}

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

bool checkEnd(int x, int y){
	return (x == n-1 && y == n-1);
}

int laymax(int a, int b){
	return a > b ? a : b;
}

void bfs(int min){
	int a = maxTs - min;
	if(a < 0) a = 0;
	while(a <= minTs){
		resetVisit();
		int b = a+min;
		front = 0; rear = 0;
		queueX[rear] = 0;
		queueY[rear++] = 0;
		visit[0][0] = 1;
		while(front < rear){
			int x = queueX[front];
			int y = queueY[front++];
			for(int i = 0; i < 4; i++){
				int xx = x + dx[i];
				int yy = y + dy[i];
				if(checkBien(xx, yy) && visit[xx][yy] == 0 && arr[xx][yy] >= a && arr[xx][yy] <= b){
					visit[xx][yy] = 1;
					if(xx == n-1 && yy == n-1) return;
					queueX[rear] = xx;
					queueY[rear++] = yy;
				}
			}
		}
		a++;
	}
}

int main(){
	freopen("input.txt", "r", stdin);
	int T; cin >> T;
	for(int tc = 1; tc <= T; tc++){
		cin >> n;
		int max = 0, min = 9999999;
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				cin >> arr[i][j];
				if(arr[i][j] > max) max = arr[i][j];
				if(arr[i][j] < min) min = arr[i][j];
			}
		}
		int a = arr[n-1][n-1] - arr[0][0];
		if(a < 0) a *= -1;
		res = 0;
		int left = a, right = max-min;
		maxTs = laymax(arr[0][0], arr[n-1][n-1]);
		minTs = maxTs == arr[0][0] ? arr[n-1][n-1] : arr[0][0];

		while(left <= right){
			resetVisit();
			int mid = (left+right)/2;
			bfs(mid);
			if(visit[n-1][n-1] == 1){
				res = mid;
				right = mid-1;
			}
			else{
				left = mid+1;
			}
		}

		cout << "#" << tc << " " << res << endl;
	}
	return 0;
}
mario
#include <iostream>
using namespace std;

int n, m;
int xStart, yStart, xEnd, yEnd;
int res;

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

int arr[55][55];
int visit[55][55];

void resetVisit(){
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			visit[i][j] = 0;
		}
	}
}

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

void backtrack(int step, int x, int y){
	visit[x][y] = 1;
	if(checkBien(x, y-1) && visit[x][y-1] == 0 && arr[x][y-1] != 0){
		backtrack(step, x, y-1);
	}
	if(checkBien(x, y+1) && visit[x][y+1] == 0 && arr[x][y+1] != 0){
		backtrack(step, x, y+1);
	}
	for(int i = 1; i <= step; i++){
		if(checkBien(x-i, y) && visit[x-i][y] == 0 && arr[x-i][y] != 0){
			backtrack(step, x-i, y);
		}
	}
	for(int i = 1; i <= step; i++){
		if(checkBien(x+i, y) && visit[x+i][y] == 0 && arr[x+i][y] != 0){
			backtrack(step, x+i, y);
		}
	}
}

int main(){
	freopen("input.txt", "r", stdin);
	int T; cin >> T;
	for(int tc = 1; tc <= T; tc++){
		cin >> n >> m;
		for(int i = 0; i < n; i++){
			for(int j = 0; 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;
				}
			}
		}


		res = 0;
		int left = 1, right = n;
		while(left <= right){
			resetVisit();
			int mid = (left+right)/2;
			backtrack(mid, xStart, yStart);
			if(visit[xEnd][yEnd] != 0){
				res = mid;
				right = mid - 1;
			}
			else{
				left = mid + 1;
			}
		}

		cout << "Case " << tc << endl;
		cout << res << endl;

	}
	return 0;
}
sumit up
#include<iostream>

using namespace std;
int matrix[50],check[50];
int t,n,ans;
bool flag;

void init(){
	cin>>t>>n;
	ans=0;
	flag=false;
	for (int i = 0; i < n; i++)
	{
		cin>>matrix[i];
	}
}

void insertionSort(int array_size) {
    int i, j, last;
    for (i=1; i < array_size; i++) {
		last = matrix[i];
        j = i;
		while ((j > 0) && (matrix[j-1] > last)) {
			matrix[j] = matrix[j-1];
			j = j - 1;
		}
        matrix[j] = last;
    } 
}
/*
void backtracking(int index, int sum){
	if(sum == t){
		ans++;
		return;
	}
	
	for (int i = index; i < n; i++)
	{
		int curSum = 0;
		if(sum < t) backtracking(index+1,sum+ matrix[i] );
	}
}
*/


void dfs(int tong, int vitri, int soPhanTuCanDeXepThanhTong){
	int i;
	if(tong>t) return;
	if(tong==t){
		flag=true;
		ans++;
		/*
		for (int i = 0; i < g-1; i++)
		{
			cout<<check[i]<<"+";
		}
		cout<<check[g-1]<<endl;
		*/

		return;
	}
	int last = -1;
	for (int i = vitri; i < n; i++)
	{
		if(tong+matrix[i] > t) continue;
		if(matrix[i] != last){
			last = check[soPhanTuCanDeXepThanhTong]= matrix[i];
			dfs(tong+matrix[i], i+1,soPhanTuCanDeXepThanhTong+1);
		}
	}
}

int main(){
	freopen("input.txt","r",stdin);
	int t;cin>>t;
	for (int i = 1; i <= t; i++)
	{
		init();
		cout<<"# "<<i<<" ";
		dfs(0,0,0);
		if(flag == false) cout<<-1<<endl;
		else if(flag == true)
		{
			cout<<ans<<endl;
		}
	//	insertionSort(n);
		//backtracking();
	}
	return 0;
}

mario
/*Mario cần phải di chuyển từ vị trí có giá trị bằng 2 và ăn vàng ở ô có giá trị bằng 3
0 là những ô Mario không thể qua
1 là những ô Mario có thể qua
2 là vị trícủa Mario
3 là vị trí Mario cần di chuyển đến
Các vị trí này được thể hiện bằng ma trận NxM( 2<=N,M<=50)
Mario có thể di chuyển theo hàng ngang hoặc hàng dọc
Hàng ngang mario chỉ nhảy được tối đa 1 bước
Hàng dọc mario có thể nhảy được “h” bước
Tìm bước nhảy “h” tối thiểu để Mario có thể ăn được vàng

Sample Input
3
5 8
1 1 1 1 0 0 0 0
0 0 0 3 0 1 1 1
1 1 1 0 0 1 0 0
0 0 0 0 0 0 1 0
2 1 1 1 1 1 1 1
5 6
0 1 1 1 0 0
3 1 0 1 1 0
0 0 0 0 1 1
0 0 0 0 0 1
2 1 1 1 1 1
9 13
0 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 0 0 0 0 0 0 0 0 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 0 1 3
0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
2 1 1 1 1 1 1 1 1 1 1 1 1

Sample output
Case #1
2
Case #2
1
Case #3
3*/
#include <iostream>
using namespace std;

#define maxN 50
#define maxQ 500000
#define inf 2147483647

int N, M, board[maxN][maxN], h, queue[maxQ][2], topQ, nQ, start[2];
bool checkBoard[maxN][maxN];
int direction[4][2] = { {0, -1}, {-1, 0}, {0, 1}, {1, 0} };

bool CheckInBoard(int row, int col)
{
	if(row < 0 || row >= N || col < 0 || col >= M) return false;
	return true;
}

bool BFS(int row, int col)
{
	for(int i = 0; i < N; ++i)
		for(int j = 0; j < M; ++j) checkBoard[i][j] = false;

	nQ = topQ = 0; queue[nQ][0] = row, queue[nQ++][1] = col; checkBoard[row][col] = true;

	while (topQ != nQ)
	{
		row = queue[topQ][0]; col = queue[topQ++][1]; 

		if(board[row][col] == 3) return true;
		for(int i = 0; i < 4; ++i)
		{
			if(i % 2 == 0)
			{
				int x = row + direction[i][0], y = col + direction[i][1];
				if(CheckInBoard(x, y) && !checkBoard[x][y] && board[x][y])
				{
					queue[nQ][0] = x, queue[nQ++][1] = y; checkBoard[x][y] = true;
					if(board[x][y] == 3) return true;
				}
			}
			else
			{
				for(int j = 1; j <= h; ++j)
				{
					int x = row + j * direction[i][0], y = col + direction[i][1];
					if(CheckInBoard(x, y) && !checkBoard[x][y] && board[x][y]) 
					{ 
						queue[nQ][0] = x, queue[nQ++][1] = y; checkBoard[x][y] = true;
						if(board[x][y] == 3) return true;
						break; 
					}
				}
			}
		}
	}
	return false;
}


int main()
{
	ios::sync_with_stdio();
	freopen("input.txt", "r", stdin);

	int T; cin >> T;
	for(int tc = 1; tc <= T; ++tc)
	{
		cin >> N >> M;
		for(int i = 0; i < N; ++i)
			for(int j = 0; j < M; ++j)
			{
				cin >> board[i][j]; 
				if(board[i][j] == 2) start[0] = i, start[1] = j;
			}


			for(h = 1; h < M; ++h)
				if(BFS(start[0], start[1])) break;

			cout << "Case #" << tc << endl << h << endl;
	}

	return 0;
}