# Untitled

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];

return false;

}

return true;

}

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

int item = dpack[k][i];

}

}

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

int item = dpack[k][i];

}

}

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];

temp += lk[item];

}

}

if (temp < minCur) {

minCur = temp;

}

return;

}

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

if (!i) {

backtrack(k + 1, cur);

} else {

backtrack(k + 1, cur + pack[0][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;

}

}

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;

} ```