[Upcoder BFS] r2.b3.Hereditament – Hereditament
Link submit: Here 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 ...
Link submit: Here
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; } |
