Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
11 kB
1
Indexable
Never
// mountain walking
#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;
}

///cach 2
#include<iostream>

using namespace std;

typedef struct{
	int x;
	int y;
}o_xy;

int Map[100][100];
o_xy Queue[100000];

bool Visited[100][100];

int n; // cap cua ma tran dau vao 
int r =-1, f =-1;

void push(o_xy value)
{
	r++;
	Queue[r] = value;
}

o_xy pop()
{
	f++;
	return Queue[f];
}

void reset()
{
	r = f = -1;
	for(int i = 0; i< 100; i++)
		for(int j =0; j< 100; j++)
			Visited[i][j] = false;
}


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

bool BFS(int low, int high)
{
	if(Map[0][0] >= low && Map[0][0] <= high)
	{

	o_xy obj;
	obj.x = 0;
	obj.y = 0;
	push(obj);
	Visited[obj.x][obj.y] = true;

	while(r!=f)
	{
		obj = pop();
		o_xy next;

		for(int i =0; i< 4; i++)
		{
			next.x = obj.x + dx[i];
			next.y = obj.y + dy[i];

			if(next.x >=0 && next.x < n && next.y >=0 && next.y < n )
			{
				if(Map[next.x][next.y] >= low && Map[next.x][next.y] <= high && !Visited[next.x][next.y])
				{
					if(next.x == n - 1 && next.y == n -1)
					{
						return true;
					}
					push(next);
					Visited[next.x][next.y] = true;
				
				}
			
			}
		}
	}
	}
	return false;
}

bool is_ok(int range, int minnn, int maxxx)
{
	for (int i = minnn; i <= maxxx - range; i++)
	{
		reset();
		if(BFS(i, i+ range))
			return true;
	
	}
	return false;
}



int main()
{
	//freopen("Text.txt","r",stdin);
	int T, maxx, minn;
	cin >> T;

	for(int tc = 1; tc <= T; tc++)
	{
		cin>>n;
		maxx = 0;
		minn = 110;
		reset();
		for(int i =0; i<n; i++)
		{
			for(int j =0; j< n; j++)
			{
				cin>>Map[i][j];
				if(Map[i][j] > maxx)
				{
					maxx = Map[i][j];
				}
				if(Map[i][j] < minn)
				{
					minn = Map[i][j];
				}
			}
		}

		int left = 0;
		int right = maxx - minn;
		int mid = 0;
		while(left <= right)
		{
			mid = (left + right)/2;
			if(is_ok(mid,minn, maxx))
			{
				right = mid -1;
			}
			else
				left = mid +1;
		}
		cout<<"#"<<tc<<" "<<left<<endl;
	}
	return 0;
}

/// cach 3
/*Cho một bản đồ kích thước NxN (2 <= N <= 100), mỗi ô mang giá trị là độ cao của ô đó (0 <= độ cao <= 110). Bác John và bò Bessie đang ở ô trên trái (dòng 1, cột 1) và muốn đi đến cabin (dòng N, cột N). Họ có thể đi sang phải, trái, lên trên và xuống dưới nhưng không thể đi theo đường chéo. Hãy giúp bác John và bò Bessie tìm đường đi sao cho chênh lệch giữa điểm cao nhất và thấp nhất trên đường đi là nhỏ nhất.
Input
Dòng 1: Số test case
Dòng 2: N
N dòng tiếp theo chứa N số nguyên, mỗi số cho biết cao độ của một ô.
Output
In ra #test case và một số nguyên là chênh lệch độ cao nhỏ nhất.

Input
5
5
1 1 3 6 8
1 2 2 5 5
4 4 0 3 3
8 0 2 3 4
4 3 0 2 1
5
99 85 38 22 55
89 28 33 3 65
99 20 14 67 90
36 27 28 77 31
50 45 12 9 14
2
92 83
19 91
5
61 49 32 34 28
100 65 0 10 89
34 99 40 86 4
10 97 49 21 30
95 33 79 51 65
2
17 60
94 27 

Output
#1 2
#2 85
#3 9
#4 50
#5 43*/
#include <iostream>
using namespace std;

#define maxN 100
#define inf 2147483647

int map[maxN][maxN], N, minMap, maxMap, min1N, max1N, queue[maxN * maxN][2], topQ, nQ, minChenhLech;
bool check[maxN][maxN];
int direction[4][2] = { {0, -1}, {-1, 0}, {0, 1}, {1, 0} };

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

void BFS(int low, int high)
{
	for(int i = 0; i < N; ++i)
		for(int j = 0; j < N; ++j) check[i][j] = false;

	topQ = nQ = 0;
	queue[nQ][0] = queue[nQ++][1] = 0;
	check[0][0] = true;

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

		if(row == N - 1 && col == N - 1)
		{
			minChenhLech = min(minChenhLech, high - low);
			return;
		}
		
		for(int i = 0; i < 4; ++i)
		{
			int x = row + direction[i][0], y = col + direction[i][1];
			if(!check[x][y] && CheckInMap(x, y) && low <= map[x][y] && map[x][y] <= high)
			{
				check[x][y] = true;
				queue[nQ][0] = x, queue[nQ++][1] = y;
			}
		}
	}
}


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

	int T; cin >> T;
	for(int tc = 1; tc <= T; ++tc)
	{
		minMap = min1N = minChenhLech = inf; maxMap = max1N = -1;

		cin >> N;
		for(int i = 0; i < N; ++i)
			for(int j = 0; j < N; ++j)
			{
				cin >> map[i][j];
				minMap = min(map[i][j], minMap);
				maxMap = max(map[i][j], maxMap);
			}

		min1N = min(map[0][0], map[N - 1][N - 1]);
		max1N = max(map[0][0], map[N - 1][N - 1]);

		for(int low = min1N; low >= minMap; --low)
			for(int high = max1N; high <= maxMap; ++high) 
				if(high - low < minChenhLech) BFS(low, high);

		cout << "#" << tc << " " << minChenhLech << endl;
	}
	return 0;
}

// dominating area
#include<iostream>
#define max 1000000
using namespace std;
int n;
int queue[2][max];
int front =-1 ;
int rear=-1;
int map[105][105];
int mapCop[105][105];
int visit[105][105];
int di[4]={0, 0, 1, -1};
int dj[4]={1,-1, 0,  0};
int ans; 
int tanso[6];

void push(int i, int j){
	if(rear == max-1) rear =-1;
	rear++;
	queue[0][rear]=i;
	queue[1][rear]=j;
}
void pop(){
	if(front == max-1) front =-1;
	front++;
}
bool IsEmpty(){
	return front == rear;
}

bool checkIn(int i, int j){
	if(i>=0 && i < n && j >=0 && j < n) return true;
	return false;
}
void Reset() {
	front=rear=-1;
	for(int i=0; i <105 ; i++){
			for(int j=0; j<105; j++){
				visit[i][j] =0;
			}
	}
	for(int i=0; i <6 ; i++){
		tanso[i]=0;
	}
}

// to color all neighbor of (i,j)
void spreadColor(int i, int j ,int color){
	for(int a=0; a<4; a++){
			int i2 = i + di[a];
			int j2 = j + dj[a];
			if(checkIn(i2, j2) && visit[i2][j2] ==0 && map[i2][j2] ==0){
				visit[i2][j2] =1;
				mapCop[i2][j2] = color;
				spreadColor(i2,j2,color);
			}
	}
}

// travel all neighbor of 0 -> count neighbor's frequency
void bfs( int i ,int j){
	Reset();
	push(i,j);
	visit[i][j] =1;

	while(!IsEmpty()){
		pop();
		int i1=queue[0][front];
		int j1=queue[1][front];
		for(int a=0; a<4; a++){
			int i2 = i1 + di[a];
			int j2 = j1 + dj[a];
			if(checkIn(i2, j2) && visit[i2][j2] ==0){
				if(map[i1][j1] == 0 || map[i2][j2] == map[i1][j1]){
					tanso[map[i2][j2]] ++;
					visit[i2][j2]=1;
					push(i2,j2);
				}
			}
		}
	}

	//  find color X that has max frequency
	int maxTS = tanso[1], color = 1;
	for (int i = 2; i <= 5; i++)
		if (tanso[i] >= maxTS) {              // Chon ra so co tan so xuat hien nhieu nhat
			color = i;
			maxTS = tanso[i];
		}
	// convert group 0 to group X
	mapCop[i][j] = color;
	spreadColor(i, j , color);
}

// need to visit all group 0 and convert them 
void Try(){
	for(int i=0; i <n ; i++){
		for(int j=0; j<n; j++){
			if(mapCop[i][j] == 0){
				bfs(i,j);
			}
		}
	}
}

void dem(){
	Reset();
	for(int i=0; i <n ; i++){
		for(int j=0; j<n; j++){
			if(visit[i][j] ==0){
				push(i,j);
				visit[i][j] =1;
				ans++;
				while(!IsEmpty()){
					pop();
					int i1=queue[0][front];
					int j1=queue[1][front];
					for(int a=0; a<4; a++){
						int i2 = i1 + di[a];
						int j2 = j1 + dj[a];
						if(mapCop[i2][j2] == mapCop[i1][j1] && visit[i2][j2] == 0) {
							visit[i2][j2] =1;
							push(i2,j2);
						}
					}
				}
			}
		}
	}
}

int main(){
	//freopen("Text.txt" ,"r", stdin);
	int test;
	cin >> test;
	for(int tc=1; tc <= test; tc++){
		cin >> n ;
		for(int i=0; i <105 ; i++){
			for(int j=0; j<105; j++){
				mapCop[i][j] = map[i][j]=0;
			}
		}
		for(int i=0; i <n ; i++){
			for(int j=0; j<n; j++){
				cin >> map[i][j];
				mapCop[i][j] = map[i][j];
			}
		}

		ans =0;
		Try();	
		dem();
		cout << "Case #" << tc << endl;
		cout << ans << endl;
	}
	return 0;
}
// ad schedule
#include <iostream>
using namespace std;
int so_khach;
int durations[4], point[4];
int time_dem[101], time_di[101];
int start_qc[4];
int end_qc[4];
int point_qc[4];
int visit[4], answer;
void tinh(int dem){
	int tong = 0;
	for(int i = 0; i < so_khach; i++){
		int tmp = 0;
		for(int j = 0; j < dem; j++){
			if(start_qc[j] >= time_dem[i] && end_qc[j] <= time_di[i]){
				if(point_qc[j] > tmp){
					tmp = point_qc[j];
				}
			}
		}
		tong = tong + tmp;
	}
	if(tong > answer)
		answer = tong;
}
void backtrack(int time, int dem){
	if(time > 50 || dem == 3){
		tinh(dem);
		return;
	}
	backtrack(time+1, dem);
	for(int i = 0; i < 3; i++){
		if(visit[i] == 0){
			visit[i] = 1;
			start_qc[dem] = time;
			end_qc[dem] = time+durations[i];
			point_qc[dem] = point[i];
			backtrack(time+durations[i], dem + 1);
			visit[i] = 0;
		}
	}
}
int main(){
	//freopen("Text.txt", "r", stdin);
	int T; cin >> T;
	for(int tc = 1; tc <= T; tc++){
		cin >> so_khach;
		for(int i = 0; i < 3; i++){
			cin >> durations[i];
			visit[i] = 0;
		}
		for(int i = 0; i < 3; i++){
			cin >> point[i];
		}
		for(int i = 0; i < so_khach; i++){
			cin >> time_dem[i];
			cin >> time_di[i];
			time_di[i] += time_dem[i];
		}
		answer = 0;
		backtrack(1, 0);
		cout << "Case #" << tc << endl << answer << endl;
	}
	return 0;
}