Link Sub: http://www.spoj.com/PTIT/problems/P166SUMH/
Người Gửi: Dương Lee
- Problem:
Sau khi giải cứu Gotham khỏi Joker và nhận tội thay Harvey Dent, Batman quyết định nghỉ hưu. Trong lúc rảnh rỗi anh ra ngoài bắt Pokemon và thi đấu với các dối thủ để lên level. Hôm nay anh đến hội trường để thi đấu ,hội trường thi đấu là một ma trận R * S, mỗi ô dành cho một huấn luận viên Pokemon, mỗi huấn luận viên có thể thi đấu với 8 đấu thủ xung quanh.
Vì mải mê bắt Pokemon, Batman đến hội trường muộn nhất, anh muốn chọn vị trí nào để anh có thể đấu với nhiều đối thủ nhất (nếu vị trí đấy trống), nếu không có vị trí nào trống anh quyết định đi loang quanh đẻ bắt Pokemon tiếp.
Hãy tính số trận đấu có thể diễn ra giữa tất cả các đối thủ.
Input |
| P166SUMH - ROUND 6H - Batman |
Hãy tính số trận đấu có thể diễn ra giữa tất cả các đối thủ.
Dòng đầu tiên chứa hai số nguyên R, S (1 <= R,S <= 50).
R dòng tiếp theo mỗi dòng chứa S ký tự thể hiện hàng thứ R, ký tự ‘.’ Thể hiện chỗ đó chưa có ai, và ‘o’ nếu đã có người chọn vị trí đó.
R dòng tiếp theo mỗi dòng chứa S ký tự thể hiện hàng thứ R, ký tự ‘.’ Thể hiện chỗ đó chưa có ai, và ‘o’ nếu đã có người chọn vị trí đó.
Output
Example:
In ra kết quả bài toán.
Input
2 3
..o
o..
Output:
2
- Solution:
Bài này có khá nhiều cách làm vậy nên mình sẽ đưa ra cách làm phổ thông nhất.
- Nhập: Nhập dữ liệu thông thường, đồng thời tạo một mảng số thứ tự (STT). Mảng này là đánh dấu dấu riêng biệt các ô, VD: input R=2 S=3 ta có mảng STT là:
1 2 3
4 5 6
- Tìm vị trí ngồi cho Batman: Cái này thì dễ rồi, chỉ cần duyệt tám hướng xung quanh và đếm xem trong 8 hướng xung quanh đó có bao nhiêu vị trí là đối thủ đang ngồi. Vị trí ngồi của Batman là vị trí có xung quanh có nhiều đối thủ nhất.
- Xét vị trí ngồi cho Batman nếu có: Bước này thực chất là thay '.'->'o' trên mảng tại vị trí đã xác định được đó là chỗ ngồi đấu được nhiều nhất.
- Đếm số trận đấu diễn ra: Ở đây có hai cách:
+ C1: là bạn chỉ cần duyệt một nửa hướng là trên xuống và đếm.
+ C2: như code dưới đây, Sử dụng một mảng check để xét xem cặp stt nào đã đấu rồi. VD:
Đang xét STT = 1 đấu với STT = 2, nếu check[1][2]=0 thì có nghĩa là cặp này chưa đấu, thì ta tăng biến đếm và set: check[1][2]=1 và check[2][1]=1. -> điều này đồng nghĩa với việc khi xét đến STT=2 sẽ loại đi được cặp 1-2 đã xét rồi.
- Nhập: Nhập dữ liệu thông thường, đồng thời tạo một mảng số thứ tự (STT). Mảng này là đánh dấu dấu riêng biệt các ô, VD: input R=2 S=3 ta có mảng STT là:
1 2 3
4 5 6
- Tìm vị trí ngồi cho Batman: Cái này thì dễ rồi, chỉ cần duyệt tám hướng xung quanh và đếm xem trong 8 hướng xung quanh đó có bao nhiêu vị trí là đối thủ đang ngồi. Vị trí ngồi của Batman là vị trí có xung quanh có nhiều đối thủ nhất.
- Xét vị trí ngồi cho Batman nếu có: Bước này thực chất là thay '.'->'o' trên mảng tại vị trí đã xác định được đó là chỗ ngồi đấu được nhiều nhất.
- Đếm số trận đấu diễn ra: Ở đây có hai cách:
+ C1: là bạn chỉ cần duyệt một nửa hướng là trên xuống và đếm.
+ C2: như code dưới đây, Sử dụng một mảng check để xét xem cặp stt nào đã đấu rồi. VD:
Đang xét STT = 1 đấu với STT = 2, nếu check[1][2]=0 thì có nghĩa là cặp này chưa đấu, thì ta tăng biến đếm và set: check[1][2]=1 và check[2][1]=1. -> điều này đồng nghĩa với việc khi xét đến STT=2 sẽ loại đi được cặp 1-2 đã xét rồi.
- Code:
C++:
https://ideone.com/df3GKj
#include <iostream>
using namespace std;
int check[2502][2502]={0};
int main ()
{
int R, S;
cin>>R>>S;
char HT[51][51]; //HT == Hoi truong :v
int STT[51][51];
int stt = 1;
for (int i=1; i<=R; i++)
for (int j=1; j<=S; j++)
{
cin>>HT[i][j];
STT[i][j] = stt;
stt++;
}
int x_xq[] = {-1, -1, +0, +1, +1, +1, +0, -1};
int y_xq[] = {+0, +1, +1, +1, +0, -1, -1, -1};
int gt_M = -1, i_M = 0, j_M = 0;
for (int i=1; i<=R; i++)
{
for (int j=1; j<=S; j++)
{
if (HT[i][j]=='.')
{
int d = 0;
for (int t=0; t<8; t++)
{
int x_m = x_xq[t]+j;
int y_m = y_xq[t]+i;
if (x_m>=1 && x_m<=S && y_m>=1 && y_m<=R && HT[y_m][x_m]=='o')
d++;
}
if (d>gt_M)
{
gt_M = d;
i_M = i;
j_M = j;
}
}
}
}
if (gt_M!=-1)
HT[i_M][j_M] = 'o';
int count = 0;
for (int i=1; i<=R; i++)
{
for (int j=1; j<=S; j++)
{
if (HT[i][j]=='o')
{
for (int t=0; t<8; t++)
{
int x_m = x_xq[t]+j;
int y_m = y_xq[t]+i;
if (x_m>=1 && x_m<=S && y_m>=1 && y_m<=R && HT[y_m][x_m]=='o')
{
if (check[STT[i][j]][STT[y_m][x_m]]==0)
{
count++;
check[STT[i][j]][STT[y_m][x_m]]=1;
check[STT[y_m][x_m]][STT[i][j]]=1;
}
}
}
}
}
}
cout<<count;
return 0;
}JAVA:
...Python:
...