Thuật toán

Chia sẻ đầy đủ về các thuật toán và lời giải các bài toán cơ bản

SPOJ.COM – Thuật toán bài HERDING – Herding

Đề bài:

Có một lượng mèo bị lạc trong thành phố. Và bạn được giao nhiệm vụ để tìm lại được hết số mèo. Đây là cơ hội lý tưởng cho bạn để kiểm nghiệm phát minh mới nhất của bạn. Một cái bẫy mèo đảm bảo sẽ bắt được những chú mèo khi nó đi vào khu vực của thành phố.

May mắn thay, bạn được trợ giúp bởi một trong những nhà tâm lý học hàng đầu về mèo – người có khả năng kì diệu về tài tiên đoán. Cho trước một vùng hình vuông trong thành phố, và chính xác 4 hướng con mèo sẽ đi (đông, tây, nam, bắc). Trong khi những thông tin này là trong tầm tay, bạn vẫn không thể biết được những nơi mà hiện tại con mèo đang ở.

Để chứng minh tính hiệu quả về giá của phương pháp này, và dĩ nhiên là tối thiểu hoá những cái bẫy sẽ được sử dụng.

Đầu vào:

Bắt đầu là một dòng gồm 2 số n và m, cách nhau bởi dấu cách,1 ≤ n, m ≤ 1000. Khu vực sẽ có kích thước nxm. n dòng tiếp theo, mỗi dòng có m kí tự, gồm 4 loại ‘N’, ‘E’, ‘S’, và ‘W’ biểu diễn hướng Bắc, Đông, Nam, Tây. Kí tự đầu tiên của dòng đầu tiên sẽ là điểm trên cùng bên trái. Hướng trên mỗi ô vuông sẽ là hướng con mèo sẽ đi, nếu con mèo ở ô đó. Đảm bảo rằng con mèo sẽ không ra khỏi thành phố.

Đầu ra:

In ra số lượng bẫy tối thiểu.

Ví dụ:

Đầu vào:

3 4
SWWW
SEWN
EEEN

Đầu ra:

2

Các bạn có thể tham khảo link gốc đề bài và submit code tại đây: http://www.spoj.com/problems/HERDING/

Phân tích:

+ Tôi nhận thấy rằng là khi con mèo đi vào thành phố, cách nó đi chính là hướng được ghi tại ô vuông nó đang đứng. Tức là hướng đã xác định trước. Do đó, để tìm được số lượng bẫy tối thiểu thì tôi phải đặt bẫy làm sao mà nó ở đúng vị trí mà chắc chắn con mèo sẽ phải đi qua đó.

+ Do đó, tôi sẽ sử dụng thuật toán tìm kiếm theo chiều sâu DFS để xác định các đường đi đó. Mỗi đường đi tôi chỉ cần đặt một cái bẫy là đủ để có thể bắt được hết số mèo.

+ Xin mời bạn theo dõi code của tôi phía dưới đây và cùng tìm hiểu xem thế nào nhé.

Lời giải:

(Các bạn nên tự mình nghĩ ra thuật toán của bài toán trước khi tham khảo code của tôi nhé. Hãy phát huy tối đa khả năng sáng tạo của bản thân. Hơn nữa code tôi viết ra cũng chưa thật sự tối ưu. Nên rất mong nhận được sự chia sẻ của các bạn.)

Code C/C++:

#include<iostream>
using namespace std;

const int MAX = 1005;
const int W   = 0;
const int N   = 1;
const int E   = 2;
const int S   = 3;

int n, m, cnt;
int Matrix[MAX][MAX], Mark[MAX][MAX];

int drow[] = { 0,-1,0, 1};
int dcol[] = {-1, 0,1, 0};

bool Check(int dir, int r, int c)
{
    if(dir == W && Matrix[r][c] == E) return true;
    if(dir == E && Matrix[r][c] == W) return true;
    if(dir == S && Matrix[r][c] == N) return true;
    if(dir == N && Matrix[r][c] == S) return true;
    return false;
}

void DFS(int row, int col)
{
    for(int i = 0; i < 4; i++)
    {
        int r = row + drow[i];
        int c = col + dcol[i];
        if(r >= 0 && r < n && c >= 0 && c < m && Mark[r][c] == 0 
        && (i == Matrix[row][col] || Check(i, r, c)))
        {
            Mark[r][c] = 1;
            DFS(r,c);
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
//    freopen("input.txt","r",stdin);
    cnt = 0;
    cin >> n >> m;
    for(int i = 0; i < n; i++)
    {
        char temp[MAX];
        cin >> temp;
        for(int j = 0; j < m; j++)
        {
            if(temp[j] == 'W') Matrix[i][j] = W;
            else if(temp[j] == 'N') Matrix[i][j] = N;
            else if(temp[j] == 'E') Matrix[i][j] = E;
            else if(temp[j] == 'S') Matrix[i][j] = S;
            Mark[i][j] = 0;
        }
    }
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
        {
            if(Mark[i][j] == 0)
            {
                Mark[i][j] = 1;
                DFS(i,j);
                cnt++;
            }
        }
    cout << cnt << endl;
    return 0;
}

Code by Phạm Văn Lâm.

198 views

1 bình luận

  1. Phạm Văn Lâm

    Trên đây là đề bài và lời giải bài HERDING – Herding trên trang spoj.com. Rất mong nhận được sự ủng hộ và phản hồi từ các bạn.

    Trân trọng,
    Phạm Văn Lâm.

Để lại bình luận

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 *