code nuoc bien, domino, quan tuong, con voi

 avatar
unknown
plain_text
2 years ago
5.8 kB
11
Indexable
#include <iostream>
using namespace std;

int map[105][105];
int vis[105][105];
int N,M;

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

void DFS_water(int r, int c, int water){
	vis[r][c] = 1;
	for (int k = 0; k < 4; k++)
	{
		int x = r + dx[k];
		int y = c + dy[k];
		if (x <0 || x >= N || y<0 ||y >=M || vis[x][y] !=0)
			continue;
		if (map[x][y] <= water)
		{
			vis[x][y] = 1;
			DFS_water(x,y,water);
		}
	}
}

void DFS_island(int r, int c)
{
	vis[r][c] =1;
	for (int k = 0; k < 4; k++)
	{
		int x = r + dx[k];
		int y = c + dy[k];
		if (x <0 || x >= N || y<0 ||y >=M || vis[x][y] !=0)
			continue;
		DFS_island(x,y);
	}
}

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

int main(){
	freopen("input.txt","r",stdin);
	cin>>N>>M;
	int tc =0;
	while (N!=0 && M!=0)
	{
		tc++;
		int low = 1000, high = -1;
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < M; j++)
			{
				cin>>map[i][j];
				if(map[i][j] < low) low = map[i][j];
				if(map[i][j] > high) high = map[i][j];
			}
		}

		int ans =-1;

		for (int water = low; water <= high; water++)
		{
			clear_vis();

			for (int i = 0; i < N; i++)
			{
				for (int j = 0; j < M; j++)
				{
					if ((i==0 || i == N-1 || j == 0 || j == M-1) && map[i][j] <= water)
					{
						if (vis[i][j] == 0)
						{
							DFS_water(i,j,water);
						}

					}
				}
			}
			int dem =0;
			for (int i = 0; i < N; i++)
			{
				for (int j = 0; j < M; j++)
				{
					if (vis[i][j] ==0)
					{
						DFS_island(i,j);
						dem++;
					}
				}

			}

			if (dem > 1)
			{
				ans = water;
				break;
			}
		}
		if (ans == -1)
		{
			cout<<"Case "<<tc<<": Island never splits."<<endl;
		}
		else
		{
			cout<<"Case "<<tc<<": Island splits when ocean rises "<<ans<<" feet."<<endl;
		}
		cin>>N>>M;
	}

return 0;
}















Domino
// cach cua Minh 
#include <iostream>
using namespace std;

int map[7][8];
int vis_domino[7][7];
int vis_map[7][8];
int ans;

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

void backTrack(int k){
	if (k == 56)
	{
		ans++;
		return;
	}
	int r = k/8;
	int c = k%8;
	if (vis_map[r][c] == 1)
	{
		backTrack(k+1);
	}
	else
	{
		for (int t = 0; t < 2; t++)
		{
			int rr = r + dx[t];
			int cc = c + dy[t];
			if (rr >= 7 || cc>= 8 || vis_map[rr][cc] == 1)
			{
				continue;
			}
			if (vis_domino[map[r][c]][map[rr][cc]] == 0 || vis_domino[map[rr][cc]][map[r][c]] == 0)
			{
				vis_domino[map[r][c]][map[rr][cc]] = 1;
				vis_domino[map[rr][cc]][map[r][c]] = 1;
				vis_map[r][c] = vis_map[rr][cc] = 1;
				backTrack(k+1);
				vis_domino[map[r][c]][map[rr][cc]] = 0;
				vis_domino[map[rr][cc]][map[r][c]] = 0;
				vis_map[r][c] = vis_map[rr][cc] = 0;

			}
		}
	}

}

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];
			}
		}
		ans =0;
		backTrack(0);
		cout<<"Case #"<<tc<<endl<<ans<<endl;
	}

return 0;
}






Quan tuong
#include <iostream>
using namespace std;

//int map[205][205];
int vis[205][205];
int N,m,p,q,s,t;
int pos[205][2];

int Qx[1000000];
int Qy[1000000];
int top, bot;

bool is_Empty(){
	return top == bot;
}

void push(int x, int y){
	top++;
	Qx[top] = x;
	Qy[top] = y;
}

void pop(){
	bot++;
}

void reset(){
	top = bot = -1;
}

void clear(){
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			//map[i][j] = 0;
			vis[i][j] = -1;
		}
	}
}

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

void BFS(){
	push(p,q);
	vis[p][q] = 0;
	while (!is_Empty())
	{
		int x = Qx[bot+1];
		int y = Qy[bot+1];
		pop();

		for (int k = 0; k < 4; k++)
		{
			int xx = x;
			int yy = y;
			while (true)
			{
				xx += dx[k];
				yy += dy[k];
				if(xx<1||xx>N||yy<1||yy>N || vis[xx][yy] == -2){
					break;
				}
				else if (vis[xx][yy] > vis[x][y] +1 || vis[xx][yy] == -1)
				{
					vis[xx][yy] = vis[x][y] +1;
					push(xx,yy);
				}
			}
		}
	}
}


int main(){
	freopen("input.txt","r",stdin);
	int T;
	cin>>T;
	for (int tc = 1; tc <= T; tc++)
	{
		cin>>N>>m>>p>>q>>s>>t;
		//reset
		reset();
		clear();

		for (int i = 1; i <= m; i++)
		{
			cin>>pos[i][0]>>pos[i][1];
			vis[pos[i][0]][pos[i][1]] = -2;
		}
		BFS();

		cout<<vis[s][t]<<endl;
	}

	return 0;
}






Con voi
#include <iostream>
using namespace std;

int N,K,M;
int R[20];
int ans;

bool check(){
	bool q = true;
	for (int i = 0; i <= N-K; i++)
	{
		int r_max = 0;
		int count = 0;
		for (int j = i; j <= i + K-1; j++)
		{
			if (R[j] > r_max)
			{
				r_max = R[j];
				count = 1;
			}
			else if (R[j] == r_max)
			{
				count++;
			}
		}
		if (count >= M)
		{
			q = false;
			break;
		}
	}
	return q;
}

void backTrack(int x, int sum){
	if (sum > ans)
	{
		return;
	}
	if (check())
	{
		if(sum< ans) ans = sum;
		return;
	}
	if (x == N)
	{
		return;
	}
	for (int i = 0; i < 2; i++)
	{
		if (i == 0)
		{
			backTrack(x+1,sum);
		}
		if (i == 1)
		{
			R[x]++;
			backTrack(x+1, sum+1);
			R[x]--;
		}
	}
}

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

		for (int i = 0; i < N; i++)
		{
			cin>>R[i];
		}
		if (M != 1)
		{
			ans = 10000;
			backTrack(0,0);
			if(ans != 10000) cout<<"#"<<tc<<" "<<ans<<endl;
			else  cout<<"#"<<tc<<" "<<-1<<endl;
		}
		else
		{
			cout<<"#"<<tc<<" "<<-1<<endl;
		} 
	}
	return 0;
}
Editor is loading...