Untitled

mail@pastecode.io avatar
unknown
plain_text
13 days ago
10 kB
3
Indexable
Never
#include<iostream>

using namespace std;

int n;

int a[210000];

int maxP;



int check(int st, int en, int mid){

	int sum1 = 0;

	int sum2 = 0;

	for(int i = st; i <= mid; i++) 

		sum1 += a[i];



	for(int i = mid + 1; i <= en; i++)

		sum2 += a[i];



	if(sum1 == sum2) return 0;

	else if(sum1 > sum2) return -1;

	else return 1;

}



int binarySearch(int st, int en){

	int low = st;

	int high = en;

	while (low <= high)

	{

		int mid = low + (high - low) / 2;

		int res = check(st, en, mid);

		if(res == 0) return mid;

		else if( res == -1) high = mid - 1;

		else low = mid + 1;

	}

	return -1;

}



void backTrack(int st, int en, int p){

	if(p > maxP)

		maxP = p;

	int mid = binarySearch(st, en);

	if (mid != -1) {

		backTrack(st, mid, p + 1);

		backTrack(mid + 1, en, p + 1);

	}

}



int main(){

	//freopen("Text.txt","r", stdin);

	int T;

	cin >>T;

	

	for(int t = 1; t <= T; t++) {

		cin >> n;

		int cnt = 0;

		for(int i =0; i < n; i++) 

		{

			cin >> a[i];

			if (a[i] == 0) 

				cnt++;

		}

		if (cnt == n) {

			cout << n -1 << endl;

		} else {

			maxP  = 0;

			backTrack(0, n - 1, 0);

			cout << maxP << endl;

		}



	}



	return 0;

}



//NangCapMayTinh

#include<iostream>

using namespace std;



int tc, m, n, l, minCur;

int lk[22], pack[2][32], dpack[32][22], lkc[22], curBuy[22];





bool check() {

	for (int i = 1; i < 1 + l; i++) {

		int item = lkc[i];

		if (curBuy[item] == 0)

			return false;

	}

	return true;

}



void buy(int k) {

	for (int i = 0; i < pack[1][k]; i++) {

		int item = dpack[k][i];

		curBuy[item] += 1;

	}

}



void unBuy(int k) {

	for (int i = 0; i < pack[1][k]; i++) {

		int item = dpack[k][i];

		curBuy[item] -= 1;

	}

}



void backtrack(int k, int cur){

	if(cur>minCur) return;

	if(check()){

		if(cur<minCur) minCur=cur;

		return;

	}

	if(k==m){

		int temp = cur;

		for (int i = 1; i < 1 + l; i++) {

			int item = lkc[i];

			if (curBuy[item] == 0) {

				temp += lk[item];

			}

		}

		if (temp < minCur) {

			minCur = temp;

		}

		return;

	}

	for (int i = 0; i < 2; i++) {

		if (!i) {

			backtrack(k + 1, cur);

		} else {

			buy(k);

			backtrack(k + 1, cur + pack[0][k]);

			unBuy(k);

		}

	}



}



int main(){

	//freopen("input2.txt","r", stdin);

	cin>>tc;

	for(int t=1; t<= tc; t++){

		cin>>n;

		for(int i=1; i<=n; i++){

			cin>>lk[i];

		}

		cin>>m;

		for(int i=0; i<m;i++){

			cin>>pack[0][i]>>pack[1][i];

			for(int j=0; j<pack[1][i]; j++){

				cin>>dpack[i][j];

			}

		}

		cin>>l;

		for(int i=1; i<=l; i++){

			cin>>lkc[i];

		}

		



		minCur = 1e9;

		backtrack(0, 0);

		cout<<"#" << t << " " << minCur<<endl;

		for(int i=0; i<l; i++) curBuy[i]=0;

		

	}



}



package Cleaning_Robot;



import java.io.FileInputStream;

import java.util.Scanner;



class Queue {

	private static final int MAX_SIZE = 1000000;

	private int[] data = new int[MAX_SIZE];

	private int front, rear;



	public Queue() {

		front = rear = -1;

	}



	boolean isEmpty() {

		return front == rear;

	}



	void enQueue(int value) {

		data[++rear] = value;

	}



	int deQueue() {

		return data[++front];

	}



	void reset() {

		front = rear = -1;

	}

}



public class Cleaning_Robot {



	static final int INF = 1000000000;

	static int N, M, startX, startY, min, countDirty; // count: dem so o ban

	static int[][] map; // luu input

	static int[][] pos; // vi tri cac o ban

	static int[][] visit;

	static int[] visited;// lan va dem kc

	static int[][] maTranKe;

	static long startFunc, endFunc;

	static Queue row = new Queue();

	static Queue col = new Queue();

	static boolean check = false, checkAll;



	static int[] r_spin = { 0, 0, -1, 1 };

	static int[] c_spin = { -1, 1, 0, 0 };



	public static void main(String[] args) throws Exception {

		System.setIn(new FileInputStream("w3_fri/Cleaning_Robot/input.txt"));

		Scanner sc = new Scanner(System.in);



		int T = sc.nextInt();

		startFunc = System.currentTimeMillis();

		for (int tc = 1; tc <= T; tc++) {

			N = sc.nextInt();

			M = sc.nextInt();



			map = new int[N][M];

			pos = new int[N * M + 1][2];

			visit = new int[N][M];

			countDirty = 1;



			for (int i = 0; i < N; i++) {

				for (int j = 0; j < M; j++) {

					map[i][j] = sc.nextInt();

					if (map[i][j] == 3) {

						pos[0][0] = i;

						pos[0][1] = j;

					}



					if (map[i][j] == 1) {

						pos[countDirty][0] = i;

						pos[countDirty][1] = j;

						countDirty++;

					}

				}

			}



			min = INF;

			checkAll = true;

			visited = new int[countDirty];

			maTranKe = new int[countDirty][countDirty];



			taoMaTranKe();



			backtrack(1, 0, 0);

			System.out.println("Case #" + tc);

			if (checkAll) {

				System.out.println(min);

			} else {

				System.out.println(-1);

			}

		}

		sc.close();

		endFunc = System.currentTimeMillis();

		System.out.println(endFunc - startFunc + " ms");

	}



	private static void taoMaTranKe() {



		for (int i = 0; i < countDirty - 1; i++) {

			for (int j = i + 1; j < countDirty; j++) {

				maTranKe[i][j] = BFS(pos[i][0], pos[i][1], pos[j][0], pos[j][1]);



				if (maTranKe[i][j] == -1) {

					checkAll = false;

				}

				maTranKe[j][i] = maTranKe[i][j];

			}

		}

	}



	private static void backtrack(int k, int cnt, int curNode) {

		if (min <= cnt) {

			return;

		}



		if (k == countDirty) {

			min = min < cnt ? min : cnt;

			return;

		}



		for (int i = 1; i < countDirty; i++) {

			if (visited[i] == 0) {

				if (maTranKe[curNode][i] != 0) {

					visited[i] = 1;

					backtrack(k + 1, cnt + maTranKe[curNode][i], i);

					visited[i] = 0;

				}

			}

		}

	}



	private static int BFS(int startRow, int startCol, int endRow, int endCol) {

		row.reset();

		col.reset();

		for (int i = 0; i < N; i++) {

			for (int j = 0; j < M; j++) {

				visit[i][j] = 0;

			}

		}



		visit[startRow][startCol] = 1;

		row.enQueue(startRow);

		col.enQueue(startCol);



		while (!row.isEmpty()) {

			int r = row.deQueue();

			int c = col.deQueue();



			for (int i = 0; i < 4; i++) {

				int newR = r + r_spin[i];

				int newC = c + c_spin[i];



				if (newR >= 0 && newC >= 0 && newR < N && newC < M) {

					if (visit[newR][newC] == 0 && map[newR][newC] != 2) {

						visit[newR][newC] = visit[r][c] + 1;

						row.enQueue(newR);

						col.enQueue(newC);

					}



					if (newR == endRow && newC == endCol) {

						return visit[r][c];

					}

				}

			}



		}

		return -1;

	}



}



//CleanRobot

#include<iostream>

using namespace std;

int n, m;

int robotX, robotY, totalDir;

const int maxS = 1e6;

int Qx[maxS];

int Qy[maxS];

int front = -1, rear = -1;

 

int step[105][105];

int distanceDir[100][100];

bool visit[100];

 

char arr[105][105];

int dirX[100];

int dirY[100];

 

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

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

 

int minStep = 100000;

 

void pop(int &x, int &y) {

	if (front == maxS - 1)front = -1;

	front++;

	x = Qx[front];

	y = Qy[front];

}

void push(int x, int y) {

	if (rear == maxS - 1)rear = -1;

	rear++;

	Qx[rear] = x;

	Qy[rear] = y;

}

bool isEmpty() {

	return rear == front;

}

bool check(int x, int y) {

	return x >= 0 && x < n&& y >= 0 && y < m;

}

void bfs(int x, int y, int currDir) {

	front = rear = -1;

	push(x, y);

	step[x][y] = 1; // mảng số bước đi

	while (!isEmpty()) {

		pop(x, y);

		

		for (int i = 0; i < 4; i++) {

			int stepx = x + dx[i];

			int stepy = y + dy[i];

			if (check(stepx, stepy) && step[stepx][stepy] == 0 && arr[stepx][stepy] != 2) {

				step[stepx][stepy] = step[x][y] + 1;

				push(stepx, stepy);

			}

		}

	}

 // Tạo ma trận kề 

	for (int i = currDir + 1; i <= totalDir; i++) {

		if (step[dirX[i]][dirY[i]] != 0) {    

			distanceDir[currDir][i] = step[dirX[i]][dirY[i]] - 1;

			distanceDir[i][currDir] = distanceDir[currDir][i];

		}

		else {

			distanceDir[currDir][i] = -1;

			distanceDir[i][currDir] = -1;

		}

	}

}

void backtrack(int currDir, int numDir, int totalStep) {

	if (numDir == totalDir) {

		if (totalStep < minStep) minStep = totalStep;

		return;

	}

	if (totalStep > minStep) return;

	for (int i = 1; i <= totalDir; i++) {

		if (!visit[i] && distanceDir[currDir][i] > 0) {

			visit[i] = true;

			backtrack(i, numDir + 1, totalStep + distanceDir[currDir][i]);

			visit[i] = false;

		}

	}

}

 

void init() {

	for (int i = 0; i < n; i++) {

		for (int j = 0; j < m; j++) {

			step[i][j] = 0;

		}

	}

}

 

int main() {

	//freopen("input.txt","r",stdin);

	while (true) {

		cin >> m >> n;

		if (m == 0 && n == 0) {

			break;

		}

		totalDir = 0;

		for (int i = 0; i <= 10; i++) {

			dirX[i] = 0;

			dirY[i] = 0;

		}

		for (int i = 0; i < n; i++) {

			for (int j = 0; j < m; j++) {

				cin >> arr[i][j];

				if (arr[i][j] == 3) {

					robotX = i; // Lưu lại tọa độ của robot

					robotY = j;

				}

				if (arr[i][j] == 1) {

					totalDir++;

					dirX[totalDir] = i; // Lưu lại tọa độ của tất cả điểm bẩn

					dirY[totalDir] = j;

				}

			}

		}

		init();

		bfs(robotX, robotY, 0); // Khoảng cách từ robot tới tất cả điểm bẩn

		for (int i = 1; i <= totalDir; i++) {

			init();

			visit[i] = false;

			bfs(dirX[i], dirY[i], i); // Khoảng cách tử các điểm bẩn tới các điểm bẩn còn lại

		}

		minStep = 100000;

		backtrack(0, 0, 0); // Tìm đường đi qua tất cả điểm bẩn có số bước đi nhỏ nhất

		if (minStep == 100000) {

			cout << -1 << endl;

		}

		else

			cout << minStep << endl;

	}

	return 0;

} 
Leave a Comment