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:

...

Author : DL

Share this

Related Posts