Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

C11POST - Dua qua

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/c11post


 Santa Khánh được giao nhiệm vụ đi phát quà trong một ngôi làng được biểu diễn bởi ma trận có độ lớn MxN từ nhà Santa Khánh đến những trẻ em trong làng. Trong ma trận có duy nhất 1 điểm là nhà của Santa Khánh ký hiệu là ‘P’, những ngôi nhà của các đứa trẻ ký hiệu là ‘K’, những điểm trống được ký hiệu là ‘.’ .Mỗi điểm được đặc trưng bởi độ cao là H[i][j]. Mỗi bước, Santa Khánh có thể đi đến những ô có điểm chung với ô đang đứng. Độ mệt mỏi bằng hiệu chênh lệch độ cao giữa điểm cao nhất và điểm thấp nhất trên đường đi. Khánh đi từ nhà của Santa Khánh đến tất cả các ngôi nhà khác của trẻ em. Do Santa Khánh phải cưỡi tuần lộc để đi phát quà, mà lũ tuần lộc ăn rất nhiều Carrot khi phải chịu độ mệt mỏi cao. Do đó Santa Khánh muốn tìm độ mệt mỏi nhỏ nhất để tích kiệm tiền mua carrot cho tuần lộc.

Input

Dòng 1: Gồm 2 số M và N ( M,N <= 100 )

M dòng tiếp theo, mỗi dòng gồm N ký tự dạng ‘P’ , ’K’ , ’.’

M dòng tiếp theo, mỗi dòng gồm N số chỉ độ cao ( 0 <= H[i][j] <= 10^9 )


 

Output

Gồm 1 số duy nhất là kết quả cần tìm.


 

Example

Input:

4 5

.....

.P...

.....

..K..

40 5 34 63 53 

6 50 99 76 64 

8 28 64 43 65 

58 54 60 15 75 

Output:

14

 

Input:
8 8
8 8 ...K.... ..K..... ........ ........ K....P.. ........ ........ ........ 6 2 2 4 3 1 9 10 10 6 8 10 7 6 2 6 4 8 9 3 6 10 7 5 5 10 7 0 6 5 2 2 0 1 2 2 3 3 5 3 2 6 9 9 5 5 9 9 7 4 7 5 7 7 6 0 4 2 3 1 6 8 1 7 Output: 8
Giới hạn: 50% số test có N,M<=60 và N*M <= 2500

Được gửi lên bởi:Duy Khanh Nguyen
Ngày:2013-11-21
Thời gian chạy:5s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED

hide comments
2023-01-25 03:04:37
:))
2018-10-27 15:06:49
111
2018-06-27 20:56:04
1 đấm AC =)))
2017-11-12 04:04:41
mất 2 ngày debug mãi 90 ko hỉu sai gì vì lộn m thành n -.-
2016-10-27 09:54:54 livw
các bạn nào làm 1 -> 2 giây thử chạy test này xem output là 1
3 3
P..
...
K..
59 1000 1000
1 60 1000
59 1000 1000
2015-03-17 11:35:07 to_yeu_mao_hieu_dong
vẫn ac mà time khủng quá
2014-12-20 07:41:19 Prismatic
=)))
2014-12-20 07:41:18 Prismatic
=)))
2014-12-19 10:53:26 Duc M. Pham
Làm bài này AC mà chạy đến 16s @@ vô list nộp bài có bạn AC mà time chỉ hơn 1s thật là bái phục

Thậm chí có bạn 0.04s @@

Last edit: 2014-12-19 15:27:40
2014-10-07 16:36:50 Kraken
time nhỏ hơn mong đợi :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.