# Untitled

unknown
plain_text
22 days ago
5.8 kB
8
Indexable
Never
```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++) {
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++) {
}
}
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;
}
```