Untitled
unknown
plain_text
a year ago
11 kB
6
Indexable
8Q, pc, clerobo, Electronic //8QueenMaxScore #include<iostream> using namespace std; int t, tc, k; int a[25][10][10], map[8][8], ans; int checkNgang(int j) { for(int x = 0; x < 8; x++) { if(map[x][j]) return 0; } return 1; } int checkCheo(int i, int j) { int x = i, y = j; while(x >= 0 && x < 8 && y >= 0 && y < 8) { if(map[x][y]) return 0; x--; y--; } x = i + 1; y = j + 1; while(x >= 0 && x < 8 && y >= 0 && y < 8) { if(map[x][y]) return 0; x++; y++; } x = i - 1; y = j + 1; while(x >= 0 && x < 8 && y >= 0 && y < 8) { if(map[x][y]) return 0; x--; y++; } x = i + 1; y = j - 1; while(x >= 0 && x < 8 && y >= 0 && y < 8) { if(map[x][y]) return 0; x++; y--; } return 1; } void initMap() { for(int i = 0; i < 8; i++) { for(int j = 0; j < 8; j++) { map[i][j] = 0; } } } void queen(int m, int i, int tong) { int diem = tong; if(i == 8) { if(diem > ans) ans = diem; return; } for(int x = 0; x < 8; x++) { if(checkNgang(x) && checkCheo(i, x)) { map[i][x] = 1; diem += a[m][i][x]; queen(m, i + 1, diem); map[i][x] = 0; diem -= a[m][i][x]; } } } int main() { //freopen("input.txt", "r", stdin); cin >> t; for(tc = 1; tc <= t; tc++) { cin >> k; int x, i, j; for(x = 0; x < k; x++) { for(i = 0; i < 8; i++) { for(j = 0; j < 8; j++) { cin >> a[x][i][j]; } } } cout << "Case #" << tc << endl; for(x = 0; x < k; x++) { ans = 0; initMap(); queen(x, 0, 0); cout << ans << 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; } //Hugo pha huy he thong dien #include<iostream> using namespace std; int tc, n, front, rear; int a[105][105], visited[105], q[10005]; void initQueue() { rear = front = -1; } int isEmpty() { return rear == front; } void enQueue(int x) { q[++rear] = x; } int deQueue() { if(!isEmpty()) { return q[++front]; } return -1; } void resetV() { for(int i = 0; i < n; i++) { visited[i] = 0; } } void BFS(int i, int x) { initQueue(); enQueue(i); visited[i] = 1; while(!isEmpty()) { int v = deQueue(); for(int u = 0; u < n; u++) { if(u != x && a[v][u] && !visited[u]) { visited[u] = 1; enQueue(u); } } } } int main() { //freopen("input.txt","r", stdin); cin >> tc; for(int t = 1; t <= tc; t++) { cin >> n; for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { cin >> a[i][j]; } } int ans = 0, index = 0; int dem; for(int x = 0; x < n; x++) { dem = 0; resetV(); for(int i = 0; i < n; i++) { if(visited[i] == 0 && i != x) { BFS(i, x); dem++; } } if(dem > ans) { ans = dem; index = x; } } if(ans == 1) index = -1; cout << index + 1 << endl; } return 0; }
Editor is loading...
Leave a Comment