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









SEA WaTER
#include <iostream>
using namespace std;

int n, m;
int seawater[102][102];
int Hmax=0;
int Hmin = 0;
void read ()
{
	for (int i=1; i<=n; i++)
	{
		for (int j=1; j<=m; j++)
		{
			cin>>seawater[i][j];
			if (seawater[i][j]>Hmax) Hmax=seawater[i][j];
			if ((i==1 || i==n || j==1 || j==m) && seawater[i][j]!=0 && seawater[i][j] < Hmin) Hmin = seawater[i][j];
		}
	}
}

int check[102][102];
int check_connect[102][102];
void init ()
{
	for (int i=1; i<=n; i++)
	{
		for (int j=1; j<=m; j++)
		{
			check[i][j]=0;
			check_connect[i][j]=0;
		}
	}
}

int extra;
int x_ar[]={+1, +0, -1, +0};
int y_ar[]={+0, -1, +0, +1};
void Spread (int i, int j)
{
	check[i][j]=1;
	for (int k=0; k<4; k++)
	{
		int X=j+x_ar[k];
		int Y=i+y_ar[k];
		if (X>=1 && X<=m && Y>=1 && Y<=n)
		{
			if (check[Y][X]==0 && seawater[Y][X]<=extra) Spread (Y, X);
		}
	}
}

// count connected component based-on BINARY matrix
void DFS (int i, int j)
{
	check_connect[i][j]=1;
	for (int k=0; k<4; k++)
	{
		int X=j+x_ar[k];
		int Y=i+y_ar[k];
		if (X>=1 && X<=m && Y>=1 && Y<=n)
		{
			if (check_connect[Y][X]==0 && check[Y][X]==check[i][j]) DFS (Y, X);
		}
	}
}

int main ()
{
	int t=0;
	while (1)
	{
		cin>>n>>m;
		if (n==0 && m==0) break;
		t++;
		read ();
		int kt=0;
		for (int k=Hmin; k<=Hmax; k++)
		{
			extra=k;
			init ();
			for (int i=1; i<=n; i++)
			{
				for (int j=1; j<=m; j++)
				{
					if ((i==1 || i==n || j==1 || j==m) && seawater[i][j]<=k && check[i][j]==0) Spread (i, j);
					
				}
			}

			//dem lien thong?
			int count_connect=0;
			for (int i=1; i<=n; i++)
			{
				for (int j=1; j<=m; j++)
				{
					if (check_connect[i][j]==0 && check[i][j]==0)
					{
						count_connect++;
						DFS (i, j);
					}
				}
			}
			if (count_connect>1)
			{
				kt=1;
				break;
			}
		}
		if (kt==1) cout<<"Case "<<t<<": Island splits when ocean rises "<<extra<<" feet."<<endl;
		else cout<<"Case "<<t<<": Island never splits."<<endl;
	}
	return 0;
}






Ice cave
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
using namespace std;
int m,n,r1,c1,r2,c2,cnt1;

int map[510][510];
int vis[510][510];
int Qx[300000];
int Qy[300000];

int f = -1; int r = -1;
void Push(int x, int y){
	r++;
	Qx[r] = x;
	Qy[r] = y;
	
}

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



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


bool isInside(int x, int y)
{
    if (x >= 0 && x < n && y >= 0 && y < m)
        return true;
    return false;
}

int nx,ny;
  int dfs(int a ,int b){
	  vis[a][b] = 1;
	  for (int i = 0; i < 4; i++)
	  {
		  nx = a + dx[i];
		  ny = b + dy[i];

		  if (isInside(nx,ny) )
		  {
			  if (nx == r2 && ny == c2)
			  {
				  if (map[r2][c2] == 0)  return 0;

				  if (map[r2][c2] == 1)  return 1;
			  }
			  
			  if (1==map[nx][ny] && vis[nx][ny] ==0)
			  {
				  vis[nx][ny] = 1;
				  dfs(nx,ny);
			  }
		  }
	  }
	  return -1;
  }

  int BFS(int r1, int c1)
{
	Push(r1,c1);
	vis[r1][c1] = 1;

	while(r != f)
	{
		Pop(r1,c1);
		for (int i = 0; i < 4; i++)
	  {
		  nx = r1 + dx[i];
		  ny = c1 + dy[i];

		  if (isInside(nx,ny) )
		  {
			  if (nx == r2 && ny == c2)
			  {
				  if (map[r2][c2] == 0)  return 0;

				  if (map[r2][c2] == 1)  return 1;
			  }
			  
			  if (1==map[nx][ny] && vis[nx][ny] ==0)
			  {
				  vis[nx][ny] = 1;
				  Push(nx,ny);
				  
			  }
		  }
	  }
		
	}
	return -1;
}

  bool neighbor(){
	  int nx, ny;
	  int cnt = 0;
	for (int i = 0; i < 4; i++)
	  {
		  nx = r2 + dx[i];
		  ny = c2 + dy[i];
		  if (map[nx][ny] == 1) cnt += 1;
	}
	return (cnt > 1);
  }
  void reset(){
	for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				map[i][j] = 0;
				vis[i][j] = 0;
			}
		}
  }

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

		// INPUT + reset test case
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
					cin>>map[i][j];
					vis[i][j] = 0;
			}
		}
		f = r = -1;
		int temp = BFS(r1,c1);

		if (temp == 0)
		{
			cout<<"YES"<<endl;
		}else if (temp == 1)
		{
			if (neighbor())
			{
				cout<<"YES"<<endl;
			}else
			{
				cout<<"NO"<<endl;
			}
		}else
		{
			cout<<"NO"<<endl;
		}

		/*if (dfs(r1,c1))
		{
			cout<<"YES"<<endl;
		}else cout<<"NO"<<endl; */

	}
return 0;
}