Untitled

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