Untitled

Color, WatSea, batcty
//Panting_ToMau
#include<iostream>

using namespace std;
int tc, n, cnt; //cnt so cach to mau
bool adj[30][30]; //true nghia la dinh i va j ke nhau
int color[30]; //color[i] la mau da to cho vung i
void backtrack(int i) {
 if(i == n) { //da to du mau cho n dinh, tang so cah len 1
  cnt++;
  return;
 }
 bool valid[4] = {
  true
 }; //mang trang thai co dung duoc hay khong cua cac mau
 for(int j = 0; j < 4; j++) valid[j] = true;
 //kiem tra tat ca cac vung ben canh va da duoc to mau
 for(int j = 0; j < i; j++) {
  if(adj[i][j]) {
   valid[color[j]] = false; //danh dau mau cua cac vung ben canh la khong dung duoc
  }
 }
 //neu mau co the to duoc, thu to mau do roi de quy tiep
 for(int j = 0; j < 4; j++) {
  if(valid[j]) {
   color[i] = j; //to mau j cho vung i
   backtrack(i + 1); //de quy cho den vung tiep theo
  }
 }
}
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 >> adj[i][j];
   }
  }
  cnt = 0;
  backtrack(0);
  cout << "Case #" << t << endl << cnt << endl;
 }
 return 0;
}

//DangNuocBien_ChiaTachDao
#include<iostream>

using namespace std;
int t, n, m, rear, front, k;
int a[101][101], visited[101][101], ngap[101][101], qX[10002], qY[10002], sX, sY, check, ans;
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};

void initQueue() {
 rear = front = -1;
}
int isEmpty() {
 if(rear == front) return 1;
 return 0;
}
void enQueue(int x, int y) {
 rear++;
 qX[rear] = x;
 qY[rear] = y;
}
int deQueueX() {
 if(!isEmpty()) return qX[front + 1];
 return -1;
}
int deQueueY() {
 if(!isEmpty()) {
  front++;
  return qY[front];
 }
 return -1;
}
void resetNgap() {
 for(int i = 0; i < n; i++) {
  for(int j = 0; j < m; j++) {
   ngap[i][j] = 0;
  }
 }
}
void resetV() {
 for(int i = 0; i < n; i++) {
  for(int j = 0; j < m; j++) {
   visited[i][j] = 0;
  }
 }
}
void BFS(int h, int i, int j) {
 initQueue();
 enQueue(i, j);
 visited[i][j] = 1;
 ngap[i][j] = 1;
 int x, y, tx, ty, k;
 while(!isEmpty()) {
  x = deQueueX();
  y = deQueueY();
  for(k = 0; k < 4; k++) {
   tx = x + dx[k];
   ty = y + dy[k];
   if(tx >= 0 && tx < n && ty >= 0 && ty < m && visited[tx][ty] == 0) {
    if(a[tx][ty] <= h) {
     enQueue(tx, ty);
     visited[tx][ty] = 1;
     ngap[tx][ty] = 1;
    } else {
     visited[tx][ty] = 1;
    }
   }
  }
 }
}
void BFS_check(int i, int j) {
 initQueue();
 enQueue(i, j);
 visited[i][j] = 1;
 int x, y, tx, ty, k;
 while(!isEmpty()) {
  x = deQueueX();
  y = deQueueY();
  for(k = 0; k < 4; k++) {
   tx = x + dx[k];
   ty = y + dy[k];
   if(tx >= 0 && tx < n && ty >= 0 && ty < m && ngap[tx][ty] == 0 && visited[tx][ty] == 0) {
    enQueue(tx, ty);
    visited[tx][ty] = 1;
   }
  }
 }
}
int main() {
 freopen("input.txt", "r", stdin);
 t = 1;
 while(true) {
  cin >> n >> m;
  if(n == 0 && m == 0) break;
  int i, j, max = 0, x;
  for(i = 0; i < n; i++) {
   for(j = 0; j < m; j++) {
    cin >> a[i][j];
    if(a[i][j] > max) {
     max = a[i][j];
    }
   }
  }
  check = true;
  ans = 0;
  for(x = 1; x < max; x++) {
   resetNgap();
   resetV();
   for(i = 0; i < n; i++) {
    for(j = 0; j < m; j++) {
     if((i == 0 || j == 0 || i == n - 1 || j == m - 1) && visited[i][j] == 0 && a[i][j] <= x) {
      BFS(x, i, j);
     }
    }
   }
   resetV();
   int dem = 0;
   for(i = 0; i < n; i++) {
    for(j = 0; j < m; j++) {
     if(dem > 1) {
      check = false;
      break;
     }
     if(ngap[i][j] == 0 && visited[i][j] == 0) {
      BFS_check(i, j);
      dem++;
     }
    }
   }
   if(!check) {
    ans = x;
    break;
   }
  }
  if(check) cout << "Case " << t << ": Island never splits." << endl;
  else cout << "Case " << t << ": Island splits when ocean rises " << ans << " feet." << endl;
  t++;
 }
 return 0;
}

//battelCiTy
#define maxN 500000#include<iostream>

using namespace std;
int QueX[maxN], QueY[maxN], a[301][301], vis[301][301];
int frontx, rearx, fronty, reary, tx, ty, u, v, tc, n, d, m, mind;
//int x1, y1;
int dx[4]={-1, 0, 1, 0};
int dy[4]={0, 1, 0, -1};

void unitQueue() {
 frontx = rearx = -1;
 fronty = reary = -1;
}
int isEmpty() {
 if(frontx == rearx && fronty == reary) return 1;
 return 0;
}
int isFull() {
 if(rearx == maxN) return 1;
 return 0;
}
void enQueue(int elementx, int elementy) {
 rearx++;
 reary++;
 QueX[rearx] = elementx;
 QueY[reary] = elementy;
}
int deQueueX() {
 if(!isEmpty()) {
  frontx++;
  return QueX[frontx];
 }
 return -1;
}
int deQueueY() {
 if(!isEmpty()) {
  fronty++;
  return QueY[fronty];
 }
 return -1;
}

bool BFS(int x, int y) {
 enQueue(x, y);
 while(!isEmpty()) {
  u = deQueueX();
  v = deQueueY();
  for(int k = 0; k < 4; k++) {
   tx = u + dx[k];
   ty = v + dy[k];
   if(tx >= 0 && tx < m && ty >= 0 && ty < n && (!vis[tx][ty] || vis[tx][ty] > vis[u][v] + 1) && a[tx][ty] <= 4) {
    vis[tx][ty] = vis[u][v] + 1;
    if(a[tx][ty] == 4) {
     vis[tx][ty]++;
    }
    if(a[tx][ty] == 2) {
     d = vis[tx][ty];
     //return 1;
    }
    enQueue(tx, ty);
   }
  }
 }
 if(vis[x1][y1]) return 1;
 return 0;
}
int main() {
 freopen("input.txt", "r", stdin);
 cin >> tc;
 for(int t = 1; t <= tc; t++) {
  cin >> m >> n;
  int x1, y1, x2, y2;
  x1 = y1 = x2 = y2 = 0;
  for(int i = 0; i < m; i++) {
   for(int j = 0; j < n; j++) {
    char c;
    cin >> c;
    if(c == 'Y') {
     a[i][j] = 1;
     x1 = i;
     y1 = j;
    } else if(c == 'T') {
     a[i][j] = 2;
     x2 = i;
     y2 = j;
    } else if(c == 'E') a[i][j] = 3;
    else if(c == 'B') a[i][j] = 4;
    else if(c == 'S') a[i][j] = 5;
    else if(c == 'R') a[i][j] = 6;
    vis[i][j] = 0;
   }
  }
  unitQueue();
  d = 0, mind = 0;
  cout << "Case #" << t << endl;
  int k = BFS(x1, y1);
  if(BFS(x1, y1)) cout << d << endl;
  else cout << -1 << endl;
 }
 return 0;
}