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