[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 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 có miếng đất hình chữ nhật ông ấy muốn chia cho K đứa con trai (1-> k)
Quá trình phân chia miếng đất to thành nhiều miếng đất nhỏ với diện tích là 1:
Đầu tiên mỗi đứa con sẽ chọn 1 miếng đất hình vuông (nghĩa là cái HCN chia thành nhiều HV có diện tích là 1)
Mỗi đứa con sẽ mở rộng mãnh đất của mình bằng cách chọn thêm 1 mãnh đất nữa mà tiếp giáp với miếng đất của mình.
Đứa con thứ 1 được chọn rồi đến thứ 2, thứ 3, thứ 4… rồi lại quay lại đứa con thứ 1 2 3 cho tới khi hết sạch miếng đấ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 inputSample output
4 7 3

1 2

3 6

4 3

11

12

5

Explanation for sample

11*11122
1111222
113222*2
333*3222

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

 

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *