Untitled
unknown
plain_text
a year ago
10 kB
7
Indexable
#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;
} Editor is loading...
Leave a Comment