Link submit: Here
Nội dung bài viết
1. Đề bài Hereditament
a. Đề Tiếng Anh
A farmer has a land in shape of rectangle has size nxm. He wants to divides his land to give to his k sons (labeled from 1 to k). Dividing process splits the land into smaller equal squares with length 1.
At first, each son will choose 1 square (No one choose same square as others). One son will expand his land by adding others square, which have same edge with their squares collected before in turn by their label until all squares are owned. It means that, they will turn around by their label to expand their land: Son with label 1 will choose first, continue with label 2,…. After label k chose, it turns again to label 1 until all squares are chosen.
Taking it faster, you suggest that you will determine number squares of each son has after this process.
b. Đề Tiếng Việt
Input
The first line of the input contains three positive integers n and m and k, where n,m ≤ 105 is the size of the land, and 2 ≤ k ≤ 10 is number of son. Next k lines each line ith contain 2 positive integers u and v that describe the location of first square of son ith by index of row and column.
Output
Output k respective lines with number of squares of each son.
Sample input | Sample output |
4 7 3 1 2 3 6 4 3 | 11 12 5 |
Explanation for sample
1 | 1* | 1 | 1 | 1 | 2 | 2 |
1 | 1 | 1 | 1 | 2 | 2 | 2 |
1 | 1 | 3 | 2 | 2 | 2* | 2 |
3 | 3 | 3* | 3 | 2 | 2 | 2 |
2. Code tham khảo Hereditament BFS
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 | #include <iostream> #include <queue> using namespace std; const long clc[] = {1,-1,0,0}; const long cld[] = {0,0,-1,1}; struct son { int x,y,id,res; son() { res = 0; } son(long X, long Y, long ID, long RES) { x=X; y=Y; id=ID; res=RES; } }; long m,n,k, tdx, tdy; son data[20]; queue<son> q; int main() { cin >> m >> n >> k; bool **free = new bool*[m+2]; for (long i = 0; i<=m+1; i++) free[i] = new bool[n+1]; for (long i=1; i<=m; i++) for (long j=1; j<=n; j++) free[i][j]=1; for (long i=0; i<=m+1; i++) { free[i][0] = false; free[i][n+1] = false; } for (long j=0; j<=n+1; j++) { free[0][j] = false; free[m+1][j] = false; } for (long i = 1; i<=k; i++) { cin >> data[i].x >> data[i].y; free[data[i].x][data[i].y] = false; data[i].id = i; data[i].res = 1; } for (long i = 1; i<=k; i++) q.push(data[i]); while (!q.empty()) { son u = q.front(); q.pop(); for (long i = 0; i<=3; i++) { tdx = u.x +cld[i]; tdy= u.y + clc[i]; if (free[tdx][tdy]) { free[tdx][tdy]=false; data[u.id].res++; q.push(son(tdx,tdy,u.id,data[u.id].res)); } } } for (long i = 1; i <= k; i++) cout << data[i].res << endl; return 0; } |
Bài viết liên quan
- [BFS] – SPOJ PPATH
- Bài 6: Thuật toán loang trên ma trận
- CRITICAL SPOJ- Thành phố trọng yếu
- C11BC2 spoj – Robin
- BCISLAND PTIT spoj – Nước biển
- [BFS] – Dhoom4 – Hackereath
- Bài 3: Danh sách kề C++ Lý thuyết đồ thị
- Bài 2: Danh sách cạnh C++ Lý thuyết đồ thị
- Bài 1: Ma trận kề C++/Pascal Lý thuyết đồ thị
- Bài 4: Thuật toán tìm kiếm theo chiều sâu DFS pascal c++