[Upcoder BFS] r2.b3.Hereditament - Hereditament

Link submit: Here

Nội dung bài viết

1. Đề bài Hereditament
- a. Đề Tiếng Anh
- b. Đề Tiếng Việt
2. Code tham khảo Hereditament BFS

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

Một ông nông dân có miếng đất hình chữ nhật ông ấy muốn chia cho K đứa con trai (1-> k)

Quá trình phân chia miếng đất to thành nhiều miếng đất nhỏ với diện tích là 1:

Đầu tiên mỗi đứa con sẽ chọn 1 miếng đất hình vuông (nghĩa là cái HCN chia thành nhiều HV có diện tích là 1)

Mỗi đứa con sẽ mở rộng mãnh đất của mình bằng cách chọn thêm 1 mãnh đất nữa mà tiếp giáp với miếng đất của mình.

Đứa con thứ 1 được chọn rồi đến thứ 2, thứ 3, thứ 4… rồi lại quay lại đứa con thứ 1 2 3 cho tới khi hết sạch miếng đất.

Input
The first line of the input contains three positive integers n and m and k, where n,m ≤ 10⁵ is the size of the land, and 2 ≤ k ≤ 10 is number of son. Next k lines each line i^th contain 2 positive integers u and v that describe the location of first square of son i^th 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

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

#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;
}

#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;

}

[Upcoder BFS] r2.b3.Hereditament – Hereditament

1. Đề bài Hereditament

a. Đề Tiếng Anh

b. Đề Tiếng Việt

2. Code tham khảo Hereditament BFS

Bài viết liên quan

Trả lời Hủy