Nội dung Bài tập
- Mã:
-
Div2.MINIGAME34.4:
CTRAVEL
- Tên:
- Đàn bò đang di chuyển (dạng 2)
- Dạng thi:
- oi
- Thang điểm:
- 10 điểm
- Giới hạn thời gian:
- 2 giây
- Giới hạn bộ nhớ:
- 256 MB
- Được tạo bởi:
- phuc
Searching for the very best grass, the cows are travelling about the pasture which is represented as a grid with N rows and M columns (2 <= N <= 100; 2 <= M <= 100). Keen observer Farmer John has recorded Bessie's position as (R1, C1) at a certain time and then as (R2, C2) exactly T (0 < T <= 15) seconds later. He's not sure if she passed through (R2, C2) before T seconds, but he knows she is there at time T.
FJ wants a program that uses this information to calculate an integer S that is the number of ways a cow can go from (R1, C1) to (R2, C2) exactly in T seconds. Every second, a cow can travel from any position to a vertically or horizontally neighboring position in the pasture each second (no resting for the cows). Of course, the pasture has trees through which no cow can travel.
Given a map with '.'s for open pasture space and '*' for trees, calculate the number of possible ways to travel from (R1, C1) to (R2, C2) in T seconds.
INPUT FORMAT: (file ctravel.in)
* Line 1: Three space-separated integers: N, M, and T* Lines 2..N+1: Line i+1 describes row i of the pasture with exactly M characters that are each '.' or '*'* Line N+2: Four space-separated integers: R1, C1, R2, and C2.
OUTPUT FORMAT: (file ctravel.out)
* Line 1: A single line with the integer S described above.
SAMPLE:
Input Output 4 5 6 ...*. ...*. ..... ..... 1 3 1 51
INPUT DETAILS:
The pasture is 4 rows by 5 colum. The cow travels from row 1, column 3 to row 1, column 5, which takes exactly 6 seconds.
OUTPUT DETAILS:
There is only one way from (1,3) to (1,5) in exactly 6 seconds (and it is the obvious one that travels around the two trees).
Đàn bò đang di chuyển trên một bãi cỏ kích thước M × N. Bãi cỏ có một số ô vuông là cây và không thể di chuyển qua nó. Tại mỗi phút, đàn bò có thể di chuyển đến 1 trong 4 ô kề cạnh, thỏa mãn chúng không bao giờ đi vào ô có cây hoặc đi ra ngoài đồng cỏ.
Nông dân John đã ghi lại được: đàn bò di chuyển từ ô (R1, C1) đến ô (R2, C2) trong đúng T phút (lũ bò có thể đến ô (R2, C2) trước đó hay không, John không thể xác định được, nhưng anh biết chắc chắn sau T phút lũ bò đang đứng tại ô (R2, C2)). Xác định số cách di chuyển thỏa mãn ghi chép của John. 2 cách di chuyển được gọi là khác nhau, nếu tồn tại một phút nào đó đàn bò di chuyển theo 2 hướng khác nhau.
INPUT: (nhập từ file ctravel.in)
• Dòng đầu tiên chứa 3 số nguyên M, N, T (2 ≤ M, N ≤ 100, 1 ≤ T ≤ 15).• Trong M dòng tiếp theo, dòng thứ k chứa xâu kí tự N chữ cái. Chữ cái '.' mô tả một ô trống, '*' mô tả một ô có cây.• Dòng tiếp theo chứa 4 số nguyên R1, C1, R2, C2. Dữ liệu đảm bảo các ô (R1, C1) và (R2, C2) là ô trống.
OUTPUT: (xuất ra file ctravel.out)
• Số cách để đàn bò di chuyển
Ví dụ:
Input Output
Theme :
Mời bạn soạn code
Ai có thể xem bài này :
Thông tin
Phần thảo luận
#include <iostream>using namespace std;struct ps { int tu, mau; &...