Untitled

Problem 1: Minimum Knight step from (x1,y1) to (x2,y2)
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;

int visit[1000][1000] = {0}; 

int Qx[1000001];
int Qy[1000001];
int Qd[1000001]; // save khoang cach tu start den diem visiting
int f = -1; int r = -1;

void Push(int x, int y, int d){
	r++;
	Qx[r] = x;
	Qy[r] = y;
	Qd[r] = d;
}

void Pop(int &x,int &y, int&d){
	f++;
	x = Qx[f];
	y = Qy[f];
	d = Qd[f];
}

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

	 bool isInside(int x, int y, int N, int M)
{
    if (x >= 1 && x <= N && y >= 1 && y <= M)
        return true;
    return false;
}
int BFS(int start[2], int end[2], int n, int m, int d){

	// push START
	Push(start[0],start[1],d);
	visit[start[0]][start[1]] = 1; // mark as visited the start
	
	while (r!=f)
	{
		Pop(start[0],start[1],d);
		// check lan can
		if (start[0] == end[0] && start[1] == end[1])
		{
			return d;
			break;
		}
		int x1,y1;
				for (int i = 0; i < 8; i++)
				{
					x1 = start[0] + dx[i];
					y1 = start[1] + dy[i];

					if (isInside(x1,y1,n,m) && !visit[x1][y1])
					{
						Push(x1,y1,d+1);
						visit[x1][y1] = 1;
					}
				}

		}
	return -1;
}


 
int main(){
	int n,m;
	int T;
	cin>>T;
	freopen("input.txt","r",stdin);
	for (int tc = 1; tc <= T; tc++)
	{
		cin>>n>>m;

		//reset
		f = r = -1;
		for (int i = 0; i <= 1000; i++)
		{
			for (int j = 0; j <= 1000; j++)
			{
				visit[i][j] = 0;
			}
		}
		// INPUT
		int Start[2];
		int End[2];
		cin>>Start[0]>>Start[1]>>End[0]>>End[1];

		cout<<"Case #"<<tc<<endl<<BFS(Start,End,n,m,0)<<endl;
	}
	return 0;
}


Bai 2: princess
#include <stdio.h>
#include <iostream>
using namespace std;
		int ans;
int visit[201][201]; 
int map[201][201];
int Qx[50000];
int Qy[50000];
int Qd[50000]; // save khoang cach tu start den diem visiting
int f = -1; int r = -1;

void Push(int x, int y, int d){
	r++;
	Qx[r] = x;
	Qy[r] = y;
	Qd[r] = d;
}

void Pop(int &x,int &y, int&d){
	f++;
	x = Qx[f];
	y = Qy[f];
	d = Qd[f];
}
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};

	 bool isInside(int x, int y, int N)
{
    if (x >= 1 && x <= N && y >= 1 && y <= N)
        return true;
    return false;
}
int BFS1(int x,int y,int n, int d){

	// push START
	Push(x,y,d);

	
	while (r!=f)
	{
		Pop(x,y,d);
		
		int x1,y1;
				for (int i = 0; i < 4; i++)
				{
					x1 = x + dx[i];
					y1 = y + dy[i];

					if (isInside(x1,y1,n)  && !visit[x1][y1] && 1==map[x1][y1]) //
					{
						Push(x1,y1,d+1);
						visit[x1][y1] = 1;
					}
					if (isInside(x1,y1,n)  && !visit[x1][y1] && 2==map[x1][y1]) //
					{
						visit[x1][y1] = 1;
						return d+1;

					}
				}
		}
	return -1;
}

 
int main(){
	int n;
	int T;
	cin>>T;
	//freopen("input.txt","r",stdin);
	for (int tc = 1; tc <= T; tc++)
	{
		cin>>n;

		//reset
		f = r = -1;
		for (int i = 1; i <= 201; i++)
		{
			for (int j = 1; j <= 201; j++)
			{
				visit[i][j] = 0;
				map[i][j] = 0;
			}
		}
		// INPUT
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				cin>>map[i][j];
			}
		}
		 ans = 0;
		int d1 = BFS1(1,1,n,0);
		//reset Queue and Visit[]
		f = r = -1;
		for (int i = 0; i < 50000; i++)
		{
			Qx[i] = Qy[i] = Qd[i] = 0;
		}
		for (int i = 1; i <= 201; i++)
		{
			for (int j = 1; j <= 201; j++)
			{
				visit[i][j] = 0;
			}
		}
		//////////////
		int d2 = BFS1(n,n,n,0);
		////////
		if (-1 == d1 || -1 == d2)
		{
			ans = -1;
		}else
		{
			ans = d1 + d2;
		}
		cout<<ans<<endl;
	}
	return 0;
}

Bai 3: 
Find cycle
Given a directed graph, check whether the graph contains a cycle or not

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

int visit[1000]; 
int v, e;

int Qx[100000];

int f = -1;
int start[1000]; 
int dest[1000]; 


void Push(int x){
	f++;
	Qx[f] = x;
}

void Pop(int &x){
	x = Qx[f];
	f--;
}


int BFS(int x){
	Push(x);
	visit[x] = 1; 
	
	while (-1!=f)
	{
		Pop(x);
		for (int i = 0; i < e; i++)
		{
			if (start[i]==x && !visit[dest[i]])
			{
				visit[dest[i]] = 1;
				Push(dest[i]);
				break;
			}
			else if (start[i]==x && visit[dest[i]])
			{
				return 1;
			}
		}
	}
	return 0;

}


 
int main(){
	int T;
	cin>>T;
	//freopen("input.txt","r",stdin);
	for (int tc = 1; tc <= T; tc++)
	{
		cin>>v>>e;

		//reset
		f  = -1;
		for (int i = 0; i <= 1000; i++)
		{
			start[i] = dest[i] = visit[i] = 0;
		}
		// INPUT
		for (int i = 0; i < e; i++)
		{
			cin>>start[i]>>dest[i];
		}

		cout<<"Case #"<<tc<<endl;
		cout<<BFS(start[0])<<endl;
	}
	return 0;
}

Bài 4: Point of balances...điểm cân bằng lực từ
#include<iostream>
#include<stdio.h>

using namespace std;
double x[15];
double weight[15];
double Answer;
int N;

double BinarySearch(double left, double right){
	double mid = (left + right) / 2;
	double F1 = 0;
	double F2 = 0;

	for(int i = 1; i<= N; i++){
		if (x[i] < mid)  F1 += weight[i]/( (mid - x[i]) * (mid - x[i]) );
		if (x[i] > mid) F2 += weight[i]/( (x[i]-mid) * (x[i]-mid) );
	}
	if ( F1 - F2 < 0.0000000001 && F1 - F2 > -0.0000000001) return mid;
	if ( F1 < F2) return BinarySearch(left,mid);
	if ( F1 > F2) return BinarySearch(mid,right); 
}

int main(int argc, char** argv)
{
	int test_case;
	int T;

	for(test_case = 1; test_case <= 10; ++test_case)
	{

		cin >> N;
		for( int i =1; i<= N; i++) cin >> x[i];
		for( int i =1; i<= N; i++) cin >> weight[i];

		printf("#%d",test_case);
		for( int i =1; i< N; i++){
			Answer = BinarySearch(x[i], x[i+1]);

			// Print the answer to standard output(screen).
			printf(" %.10lf",Answer);
		}
	 cout<<endl;

	}
	return 0;//Your program should return 0 on normal termination.
}

Bai 5 : village
Làng mạc
Cho bản đồ mạng lưới giao thông giữa các làng mạc. Một vùng được định nghĩa là một tập hợp các làng mà từ bất kỳ một làng nào trong vùng đều có thể đi đến một làng khác trong vùng.
Hãy tính số vùng trong bản đồ, số làng cô lập (làng không có đường đi đến bất kỳ làng khác) và số con đường đóng vai trò là “Cầu” giữa hai vùng (nếu bỏ con đường này đi thì số lượng vùng tăng lên 1).
Input
Dòng đầu có một số T là số lượng test của file input. Mỗi test được bố cục như sau: dòng đầu là một số nguyên dương N (N <= 300) N là số làng, tiếp theo là một ma trân A[i, j] trong đó A[i][j] có giá trị bằng 1 là có đường đi từ làng i tới làng j và 0 nếu không có đường từ làng i tới làng j. Dữ liệu đảm bảo nếu có đường từ làng i tới làng j thì cũng sẽ có đường ngược lại.
Output
Với mỗi test, in ra sốvùng có trên bản đồ, số làng cô lập và số đường đóng vai trò là cầu.


If not visited -> so vung +1
Tu input-> hàng nào toàn 00000-> ko connect any village -> alone village + 1 -> visited = true;
For	½ map
 Tim map i j = 1 (path 2 village)  delete map i j =0 -> dem lai so vung
	If new region – old region  = 1
C2:  bool bfs(i,j) -> nếu vẫn còn path i -> j   có cầu++ 

	Bridge + 1

Map I j =1 // tra lai connection




///   txt


//// path routing

#include <stdio.h>
#include <iostream>
using namespace std;

int S[1000];
int t = -1;

void Push(int x){
	S[++t] = x;
}

void Pop(int &x){
	x = S[t];
	t--;
}

//data
int M[100][2];

bool DFS(int s){
	Push(s);
	//  take mark
	// bai nay k can
	// 
	// tranverse
	while (t!=-1)
	{
		Pop(s);
		for (int i = 0; i < 2; i++)
		{
			// check lan can
			if (M[s][i] == 99) {return true;}
			if (M[s][i] != -1)
			{
				Push(M[s][i]);
				M[s][i] == -1;
			}
		}
	}
	return false;
}

int main() {
	int n;

	for (int tc = 1; tc <= 10; tc++)
	{
		//reset M[][] va Stack
		t = -1;
		for (int i = 0; i < 100; i++)
		{
			M[i][0] = M[i][1] = -1;
		}

		cin>>n>>n;
		int s;
		for (int i = 0; i < n; i++)
		{
			cin>>s;
			if (M[s][0] == -1)
			{
				cin>>M[s][0];
			}else
			{
				cin>>M[s][1];
			}
		}
		cout<<"#"<<tc<<" "<<DFS(0)<<endl;
	}
	return 0;
}

// from 2 to 3 theo line 0


#include <stdio.h>
#include <iostream>
#define MAX_STACK 10000

using namespace std;
struct Point
{
	int row;
	int col;
	Point (int r, int c){
		row = r;
		col = c;
	}
	Point (){
		row = 0;
		col = 0;
	}
};
class Stack
{
	Point A[MAX_STACK];
	
public:
	int top;
	Stack();
	~Stack();
	bool isEmpty();
	bool isFull();
	void push(Point s);
	Point pop();
	Point peak();
	void reset();
private:

};

Stack::Stack()
{
	top = -1;
}

Stack::~Stack()
{
}
bool Stack::isEmpty(){
	return (top == -1);
}

bool Stack::isFull(){
	return (top == MAX_STACK - 1);
}
void Stack::push(Point s){
	if (isFull())
	{
		//cout<<"Stack overflow";
	}
	++top;
	A[top] = s;
}

Point Stack::pop(){

	--top;
	return A[top + 1];
}
Point Stack::peak(){
	return A[top];
}

void Stack::reset(){
	top = -1;
}

Stack mStack;
char Map[100][100];
bool is_ok = false;
int rowstep[] = {0,0,-1,1};
int colstep[] = {1,-1,0,0};
int main() {
	int n;

	for (int tc = 1; tc <= 10; tc++)
	{
		is_ok = false;
		cin>>n;
		for (int i = 0; i < 100; i++)
		{
				cin>>Map[i];
		}
				mStack.reset();
		for (int i = 0; i < 100; i++)
		{
			for (int j = 0; j < 100; j++)
			{
				if (Map[i][j] == '2')
				{
					mStack.push(Point(i,j));
				}
			}
		}

		// solution
		while (!mStack.isEmpty() && !is_ok){
			Point newPoint;
			Point temp = mStack.pop();
			for (int i = 0; i < 4; i++)
			{
				newPoint = Point(temp.row + rowstep[i],temp.col + colstep[i]);
					if (Map[newPoint.row][newPoint.col]  == '3')
					{
						is_ok = true;
						break;
					}
					if (Map[newPoint.row][newPoint.col]  == '0')
					{
						mStack.push(newPoint);
						Map[newPoint.row][newPoint.col]  = '1';
					}
			}
		}
		if (is_ok)
		{
			 cout<<"#"<<tc<<" "<<1<<endl;

		}else
		{
					 cout<<"#"<<tc<<" "<<0<<endl;
		}
	}
	return 0;
}

//// contact
c1: need to pop all queue to ensure time sync
for (queue)
pop

c2: input dang point (value, number_step or time or length)

// code

#include <stdio.h>
#include <iostream>
using namespace std;
int a[1000] = {-1};
int visit[100] = {0}; 
int ds[100] = {0};
int Qx[100000];
int Qd[100000]; // save khoang cach tu start den diem visiting
int f = -1; int r = -1;

void Push(int x, int d){
	r++;
	Qx[r] = x;
	Qd[r] = d;
}

void Pop(int &x, int&d){
	f++;
	x = Qx[f];
	d = Qd[f];
}

void BFS(int x, int d, int n){

	// push START
	Push(x,d);
	visit[x] = 1; // mark as visited the start
	
	while (r!=f)
	{
		Pop(x,d);

		// check lan can
				for (int i = 1; i <= n; i+=2)
				{
					if (a[i] == x &&  1 != visit[a[i+1]] )
					{
						Push(a[i+1],d+1);
						visit[a[i+1]] = 1;
						ds[a[i+1]] = d+1;
					}
				}

		}
}

int main(){
	int n,start;
	int ans = 0;
	int d=0;
	int maxFreq = 0;
	//freopen("input.txt","r",stdin);
	for (int tc = 1; tc <= 10; tc++)
	{
		cin>>n>>start;

		//reset
		f = r = -1;
		for (int i = 0; i < 100; i++)
		{
			visit[i] = 0; 
			ds[i] = 0;
		}
		// INPUT
		for (int i = 1; i <= n; i++)
		{
			cin>>a[i];
		}
		// algorithm
		BFS(start,d,n);
		maxFreq = ds[0];
		for (int i = 1; i < 100; i++)
		{
			maxFreq = max(maxFreq,ds[i]);
		}
		
		// tim value of maxFreq --> duyet nguoc
		for (int i = 99; i >= 1; i--)
		{
			if (ds[i] == maxFreq)
			{
				ans = i;
				break;
			}
		}
		cout<<"#"<<tc<<" "<<ans<<endl;
	}
	return 0;
}

// in so thuc 10 chu so sau dau phay
//C++
cout.setf(ios::fixed);
cout.setf(ios::showpoint);
cout.precision(10);

// C
double x;
printf("%0.10lf",x);
return 0;

// farmcover

#include<iostream>
using namespace std;

const int MAX = 710;

int N,M;                
int n_Hill;             
int Map[MAX][MAX];      

bool visited[MAX][MAX];   
bool tallest;            

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


void DFS(int row, int col)
{
	
	visited[row][col] = true;

	for(int i = 0; i < 8; i++)
	{
		int r_next = row + dx[i];
		int c_next = col + dy[i];

		if(r_next >= 0 && r_next < N && c_next >= 0 && c_next < M)
		{
			// higher than current pos -> false
			if(tallest && Map[r_next][c_next] > Map[row][col]) 
				tallest = false;

			// travese all same height pos
			if(Map[r_next][c_next] == Map[row][col] && !visited[r_next][c_next]) 
				DFS(r_next, c_next);
		}
	}
}

int main()
{
	int T;
	cin >> T;


	for(int test_case = 1; test_case <= T; ++test_case)
	{
		n_Hill = 0;
	
	cin >> N >> M;
	for(int i = 0; i < N; i++)
		for(int j = 0; j < M; j++)
		{
			cin >> Map[i][j];
			visited[i][j] = false;
		}


	for(int i = 0; i < N; i++)
		for(int j = 0; j < M; j++)
			if(!visited[i][j])
			{

				tallest = true;
				DFS(i, j);
				if(tallest) n_Hill++;
			}

	
			cout <<"#"<<test_case<<" " << n_Hill << endl;
	}

	return 0;
}