P141SUMF - ROUND 1F - Ném đá

Link Sub: https://www.spoj.com/PTIT/problems/P141SUMF/
Người Gửi: Dương Lee

• Problem:

Trong khoảng 2 tuần, Zoro phải nằm trên giường vì bị bạn Nami vô tình ném 1 viên đá to vào chân trái. Vì Zoro đã hoàn thành hết nhiệm vụ nên anh ta phải tìm cách để giết thời gian.  
Trò chơi mới của Zoro được chơi trên 1 bảng kích thước R X C. Ban đầu, mỗi ô vuông được để trống hoặc bị chặn bởi 1 bức tường. Zoro ném 1 viên đá vào bảng bằng cách để nó vào hàng trên cùng của 1 cột và để trọng lực làm làm phần còn lại.  
Trọng lực hoạt động như sau: 
- Nếu ô vuông bên dưới viên đá là 1 bức tường chắn, hoặc nếu viên đá ở hàng cuối cùng của một cột thì nó ở yên chỗ đó.  
- Nếu ô vuông bên dưới viên đá để trống, nó sẽ di chuyển xuống ô đó.  
- Nếu ô vuông bên dưới viên đá, có 1 viên đá khác, viên đá có thể trượt sang 2 bên như sau:     
+ Nếu ô vuông bên trái, và ô dưới của ô bên trái trống, viên đá sẽ trượt sang ô bên trái.     
+ Nếu viên đá không trượt sang trái và ô vuông bên phải, ô dưới của ô bên phải trống, viên đá sẽ trượt sang phải.     
+ Còn lại, viên đá sẽ ở yên đó, và không di chuyển nữa.  
Zoro không bao giờ ném viên đá khác, khi viên đá trước chưa rơi cố định vào 1 ô nào đó.  
Viết 1 chương trình, vẽ cái bảng sau khi Zoro ném toàn bộ số viên đá của mình vào đó, giả sử chúng ta biết Zoro ném đá vào các cột, theo thứ tự.  
Chú ý : Zoro không bao giờ ném 1 viên đá vào 1 cột, nếu ô trên cùng của cột đó không trống.

Input

Dòng đầu tiên chứa số nguyên R và C, là kích thước của bảng (R, C <= 30).  
Mỗi dòng trong N dòng tiếp theo, chứa C kí tự, là sơ đồ ban đầu của bảng. Dấu '.' đại diện cho 1 ô trống, trong khi 'X' là 1 ô được chặn bởi tường.  
Dòng kế tiếp chứa số nguyên N, là số viên đá mà Zoro ném.  
Mỗi N dòng tiếp theo chứa 1 số nguyên giữa 1 và C, là cột mà Zoro ném viên đá vào (đánh số từ trái sang phải).

Output

In ra R dòng, mỗi dòng chứa C kí tự, là sơ đồ của bảng sau khi đã ném hết đá vào. Đá được kí hiệu bằng chữ cái “O”.

Example:

Input

5 4
....
....
X...
....
....
4
1
1
1
1

Output:

....
O...
X...
....
OOO.

Input

7 6
......
......
...XX.
......
......
.XX...
......
6
1
4
4
6
4
4

Output:

......
...O..
...XX.
......
.OO...
.XX...
O..O.O

• Solution:

Bài này sử dụng đệ quy để tìm đường tiếp theo cho viên đá (Dựa vào dữ kiện của đề cung cấp là được).
Để tiện hơn thì mình tạo thêm một hàng rào 'X' bao xung quanh nữa để đỡ phải xét nhiều điều kiện. 
VD: 
Map:
...X.
.....
Thì giờ sẽ thành:
XXXXXXX
X...X.X
X.....X
XXXXXXX

• Code:

C++:

https://ideone.com/SULbQ2

#include <iostream>
#include <vector>
using namespace std;

int r, c;
char m[35][35];
vector <int> v;

void read()
{
    cin>>r>>c;
    for (int i=0; i<=r+1; i++)
    {
        for (int j=0; j<=c+1; j++)
        {
            if (i==0 || i==r+1 || j==0 || j==c+1)
                m[i][j] = 'X';
            else
            {
                cin>>m[i][j];
            }
        }
    }

    int n;
    cin>>n;
    for (int i=0; i<n; i++)
    {
        int a;
        cin>>a;
        v.push_back(a);
    }
}

int findWay(int i, int j)
{
    if (m[i+1][j] == 'X')
    {
        m[i][j] = 'O';
        return 1;
    }
    else if (m[i+1][j] == '.')
    {
        findWay(i+1, j);
    }
    else if (m[i+1][j] == 'O')
    {
        if (m[i][j-1] == '.' && m[i+1][j-1] == '.')
        {
            findWay(i+1, j-1);
            return 1;
        }
        else if (m[i][j+1]=='.' && m[i+1][j+1] == '.')
        {
            findWay(i+1, j+1);
            return 1;
        }
        else
        {
            m[i][j] = 'O';
            return 1;
        }
    }
}

void out()
{
    for (int i=1; i<=r; i++)
    {
        for (int j=1; j<=c; j++)
        {
            cout<<m[i][j];
        }
        cout<<endl;
    }
}

void check()
{
    cout<<r<<" "<<c<<endl;
    for (int i=0; i<=r+1; i++)
    {
        for (int j=0; j<=c+1; j++)
        {
            cout<<m[i][j];
        }
        cout<<endl;
    }
    cout<<v.size()<<endl;
    for (int i=0; i<v.size(); i++)
        cout<<v[i]<<endl;
}

int main()
{
//    freopen("input.txt", "r", stdin);
    read();
    for (int i=0; i<v.size(); i++)
    {
        findWay(1, v[i]);
    }
    out();
//    check();
    return 0;
}

JAVA:

...

Python:

...

PTIT013L - BÀI L- ĐIỂM THẮT GIAO THÔNG

Link Sub: http://www.spoj.com/PTIT/problems/PTIT013L/
Người Gửi: Dương Lee

• Problem:

Cho hệ thống giao thông gồm N điểm. Biết giữa hai điểm bất kỳ của hệ thống đều tồn tại đường đi trực tiếp hoặc gián tiếp thông qua một số điểm trung gian. Ta gọi điểm giao thông s là điểm thắt của cặp nút giao thông u, v nếu mọi đường đi từ u đến v đều phải đi qua s. Ví dụ, với cặp nút 1, 3 của hệ thống giao thông gồm 5 điểm dưới đây sẽ có đỉnh thắt s = 2 và s = 4.  
Nhiệm vụ của bạn là viết một chương trình tìm số lượng các đỉnh thắt s của cặp điểm u, v của hệ thống giao thông.
Input
Dòng đầu tiên chứa số nguyên dương không lớn hơn 100 là số lượng các bộ dữ liệu. Các dòng tiếp theo chứa các bộ dữ liệu. Mỗi bộ dữ liệu gồm một nhóm dòng theo khuôn dạng:   
Dòng 1 chứa 4 số nguyên N,M,u,v (u,v,N ≤ 100; M ≤ 1000).   
M dòng  sau, mỗi dòng ghi hai  số  i,  j cách nhau một khoảng trống cho biết có đường nối trực tiếp giữa i với j (1≤i,j≤N).

Output
Với mỗi bộ dữ liệu, đưa ra màn hình một số nguyên là số lượng đỉnh thắt của cặp điểm u,v tương ứng.

Example:

Input

2
5 7 1 3
1 2
2 4
2 5
3 1
3 2
4 3
5 4
4 5 1 4
1 2
1 3
2 3
2 4
3 4

Output:

2
0

• Solution:

- Sử dụng đệ quy quay lui check các điểm duyệt tới - Các bước làm: + Xây dựng các đường đi - read () (Sử dụng danh sách kề để tối ưu time). + Khởi tạo: mark[]=1 và check[]=0 - init() (mark[] là đại diện cho các điểm trùng, check[] là đại diện cho những điểm mà nó đi qua). + Đồ thị: Sử dụng đệ quy quay lui (theo cách DFS) để duyệt toàn bộ các trường hợp đi - DQ_QL(); (Mỗi lần tìm được đường từ u->v ta thu được arr: check[]) + Tìm điểm thắt nút: Điểm thắt nút là điểm có dạng mà tất cả các đường từ u->v đều phải qua điểm đó -> Vậy với mỗi arr: check[] thu được, ta sẽ đem so sánh nó với điểm duyệt trước nó là mark[] và lưu lại các điểm trùng. VD: cho 5 đỉnh: 1 2 3 4 5 có các đường đi từ 1->3 là: check[] 1 1 1 1 0 (1->2->4->3); check[] 1 1 1 1 1 (1->2->5->4->3); thu được mark[]: >mark[] 1 1 1 1 0 Vậy rõ ràng sau khi duyệt hết đường đi thì ngoài 1 và 3 có thêm 2 và 4 luôn được duyệt -> Có 2 điểm thắt => Số điểm thắt là số điểm luôn được duyệt ngoài 2 điểm u, v;

• Code:

C++:

JAVA:

BCISLAND - Nước biển

Link Sub: http://www.spoj.com/PTIT/problems/BCISLAND/
Người Gửi: Dương Lee

• Problem:

Trái đất nóng lên kéo theo mực nước biển dâng. Hòn đảo nhỏ Gonnasinka thuê bạn để dự báo trước hiểm họa này. Cho trước 1 lưới tọa độ thể hiện cao độ của đảo, hãy giúp họ tính toán xem nước biển dâng cao bao nhiêu thì hòn đảo sẽ bị chia cắt.
Input
Input gồm nhiều bộ test, mỗi bộ test bao gồm:  
Dòng đầu ghi 2 số n, m là chiều dài và chiều rộng. 
Sau đó là n dòng, mỗi dòng gồm m số, mỗi số cho biết độ cao của ô đó, giá trị 0 chỉ mực nước biển. Những ô giá trị 0 dọc theo đường viền và những ô số 0 liền kề những ô này chỉ mặt biển. Những ô có giá trị 0 còn lại (được bao bọc bởi các số > 0) là đất liền bên trong đảo nhưng có độ cao ngang mặt nước biển. Hòn đảo lúc đầu chưa bị chia cắt. Số n và m không lớn hơn 100 và độ cao không lớn hơn 1000. 
Dòng cuối cùng của input chứa 2 số 0

Output
Với mỗi bộ test, in ra:  
Case n: Island splits when ocean raises f feet. (Đảo bị chia khi nước biển dâng cao f feet)  
Hoặc  
Case n: Island never splits. (Đảo không bao giờ bị chia cắt)

Example:

Input

5 5
3 4 3 0 0
3 5 5 4 3
2 5 4 4 3
1 3 0 0 0
1 2 1 0 0
5 5
5 5 5 5 7
4 1 1 1 4
4 1 2 1 3
7 1 0 0 4
7 3 4 4 4
0 0

Output:

Case 1: Island never splits.
Case 2: Island splits when ocean rises 3 feet.

• Solution:

- Bài này chia ra làm các bước như sau: + B1: Tìm độ cao lớn nhất so với mặt nước biển. (Hmax) + B2: Với độ cao tăng thêm: extra = 1->Hmax ta sẽ loang bắt đầu từ các cạnh là biển loang vào những nới có độ (độ cao <= extra). VD: có bản đồ: 5 5 5 5 7 4 1 1 1 4 4 1 2 1 3 7 1 0 0 4 7 3 4 4 4 với extra=1 ta thu được check[][]: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 +B3: Đếm số thành phần liên thông tại check[][] với các check[][]==0 bằng DFS; Số thành phần liên thông > 1 thì tại độ cao extra đó đảo bị chia cắt; VD: ở bản đồ trên tại extra = 3 ta có check[][]: 0 0 0 0 0 0 1 1 1 0 0 1 0 1 1 0 1 1 1 0 0 1 0 0 0

• Code:

C++:

JAVA:

BCLKCOUN - Đếm số ao

Link Sub: http://www.spoj.com/PTIT/problems/BCLKCOUN/
Người Gửi: Dương Lee

• Problem:

Sau khi kết thúc OLP Tin Học SV, một số OLP-er quyết định đầu tư thuê đất để trồng rau.

Mảnh đất thuê là một hình chữ nhật N x M (1<=N<=100; 1<=M<=100) ô đất hình vuông.

Nhưng chỉ sau đó vài ngày, trận lụt khủng khiếp đã diễn ra làm một số ô đất bị ngập :((

Due to recent rains, water has pooled in various places in Farmer

John's field, which is represented by a rectangle of N x M (1 <= N

<= 100; 1 <= M <= 100) squares. Each square contains either water

('W') or dry land ('.'). Farmer John would like to figure out how

many ponds have formed in his field.  A pond is a connected set of

squares with water in them, where a square is considered adjacent

to all eight of its neighbors.

Given a diagram of Farmer John's field, determine how many ponds he has.

PROBLEM NAME: lkcount

INPUT FORMAT:

* Line 1: Two space-separated integers: N and M

* Lines 2..N+1: M characters per line representing one row of Farmer

        John's field.  Each character is either 'W' or '.'.  The

        characters do not have spaces between them.

SAMPLE INPUT (file lkcount.in):

10 12

W........WW.

.WWW.....WWW

....WW...WW.

.........WW.

.........W..

..W......W..

.W.W.....WW.

W.W.W.....W.

.W.W......W.

..W.......W.

OUTPUT FORMAT:

* Line 1: The number of ponds in Farmer John's field.

SAMPLE OUTPUT (file lkcount.out):

3

OUTPUT DETAILS:

There are three ponds: one in the upper left, one in the lower left,

and one along the right side.

Mảnh đất biến thành một số các ao. Các OLP-er quyết định chuyển sang nuôi cá :D Vấn đề lại

nảy sinh, các OLP-er muốn biết mảnh đất chia thành bao nhiêu cái ao để có thể tính toán

nuôi trồng hợp lý. Bạn hãy giúp các bạn ý nhé.

Chú ý: Ao là gồm một số ô đất bị ngập có chung đỉnh. Dễ nhận thấy là một ô đất có thể có tối đa 8 ô chung đỉnh.

Input
* Dòng1: 2 số nguyên cách nhau bởi dấu cách: N và M      
* Dòng 2..N+1: M kí tự liên tiếp nhau mỗi dòng đại diện cho 1 hàng các ô đất.  
Mỗi kí tự là 'W' hoặc '.' tương ứng với ô đất đã bị ngập và ô đất vẫn còn nguyên.

Output
* Dòng 1: 1 dòng chứa 1 số nguyên duy nhất là số ao tạo thành.

Example:

Input

10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.

Output:

3

• Solution:

Bài này mình sử dụng phương pháp DFS đệ quy tìm số thành phần liên thông. 
Sơ lược qua về khởi tạo ban đầu: 
- Tạo dinh[R][C]: với lần lượt các đỉnh từ 1->R*C; 
- Duyệt theo 8 hướng (lên, lên trái, trái, xuống trái, xuống, xuống phải, phải, lên phải) và đánh dấu; 
Các bạn cũng có thể sử dụng BFS.

• Code:

C++:

JAVA:

BCGRASS - Bãi cỏ ngon nhất

Link Sub: http://www.spoj.com/PTIT/problems/BCGRASS/
Người Gửi: Dương Lee

• Problem:

Bessie dự định cả ngày sẽ nhai cỏ xuân và ngắm nhìn cảnh xuân trên cánh đồng của nông dân John, cánh đồng này được chia thành các ô vuông nhỏ với R (1 <= R <= 100) hàng và C (1 <= C <= 100) cột.
Bessie ước gì có thể đếm được số khóm cỏ trên cánh đồng.
Mỗi khóm cỏ trên bản đồ được đánh dấu bằng một ký tự ‘#‘ hoặc là 2 ký tự ‘#’ nằm kề nhau (trên đường chéo thì không phải).
Cho bản đồ của cánh đồng, hãy nói cho Bessie biết có bao nhiêu khóm cỏ trên cánh đồng.

Ví dụ như cánh đồng dưới dây với R=5 và C=6:

.#....

..#...

..#..#

...##.

.#....

Cánh đồng này có 5 khóm cỏ: một khóm ở hàng đầu tiên, một khóm tạo bởi hàng thứ 2 và thứ 3 ở cột thứ 2, một khóm là 1 ký tự nằm riêng rẽ ở hàng 3, một khóm tạo bởi cột thứ 4 và thứ 5 ở hàng 4, và một khóm cuối cùng ở hàng 5.

Input

• Dòng 1: 2 số nguyên cách nhau bởi dấu cách: R và C
• Dòng 2..R+1: Dòng i+1 mô tả hàng i của cánh đồng với C ký tự, các ký tự là ‘#’ hoặc ‘.’ .

Output
Dòng 1: Một số nguyên cho biết số lượng khóm cỏ trên cánh đồng.

Example:

Input

5 6
.#....
..#...
..#..#
...##.
.#....

Output:

5

• Solution:

Bài này mình sử dụng phương pháp DFS đệ quy tìm số thành phần liên thông. Sơ lược qua về khởi tạo ban đầu: 
- Tạo dinh[R][C]: với lần lượt các đỉnh từ 1->R*C; 
- Duyệt theo 4 hướng (lên, trái, xuống, phải) và đánh dấu; Các bạn cũng có thể sử dụng BFS.

• Code:

C++:

JAVA: