0 Judge
Code: 0
在這個問題中,你是一隻因公出差的螃蟹銷售員,為了到隔壁群落推銷最新款的彈塗魚乾,你必須渡過凶險的沙河。
沙河可以視作一個$N\times M$的棋盤,棋盤中每一列由上自下編號分別為$0, 1, 2, 3, ..., N-1$,每一行由左自右編號分別為$0, 1, 2, 3, ..., M-1$,第$r$列第$c$行的座標記為$(r, c)$。
所謂渡過沙河就是從棋盤上一點$(r_s, c_s)$走到目的點$(r_t, c_t)$,中途可以選擇0個或多個地點休息。
身為一名受過良好教育的螃蟹,你深知自己應該謹守螃蟹的古老訓誡,不管身處多麼嚴酷的環境都絕對不可以直著走,因此你的旅程只能由以下三種走法組成(每一種走法都可以使用多次或不使用):
如圖所示,螃蟹當前位置在(1, 2)時,灰色 / 藍色 / 紅色格子分別代表1 / 2 / 3種走法一步可以走到的休息點。
另外,由於沙河強烈的日曬與複雜的環境,隨便亂走很可能死在半途,這也是路線規畫必須考慮的問題。
為了簡化問題,沙河上座標$(r, c)$點的環境可以由潮濕度$h(r, c)$與舒適度$p(r, c)$概述,滿足下列條件的旅程規劃可以稱為一個合法螃蟹旅程:
給定起點$(r_s, c_s)$、終點$(r_t, c_t)$及沙河的大小、潮濕度及舒適度資訊,請問所有合法螃蟹旅途中,舒適度最高者有多高?
若不存在任何合法螃蟹旅程,請輸出"You are fired!"。
輸入檔案中,一個檔案只會有一筆測資。
第一行有六個整數,分別為$N$、$M$、$r_s$、$c_s$、$r_t$、$c_t$。
第二行為空白行,此行除了換行符號外不會有其他字元。
接下來的$N$行每行有$M$個整數,第$r$行的第$c$個整數代表$h(r, c)$。
再來為一空白行,此行除了換行符號外不會有其他字元。
再來有$N$行每行有$M$個整數,第$r$行的第$c$個整數代表$p(r, c)$。
若存在合法螃蟹旅程,輸出最大的舒適度。
若不存在,則輸出"You are fired!" (不含括號),請注意大小寫及標點符號必須完全一致。
輸出完後請換行。
$2 \leq N \times M \leq 10^6$
$0 \leq h(r, c) < 10^6$
$-10 < p(r, c) < 10$
$0 \leq r_s, r_t < N$
$0 \leq c_s, c_t < M$
$(r_s, c_s) \neq (r_t, c_t)$
額外限制 $N \leq 300, M \leq 300$
額外限制 $N \leq 3, M \leq 3$
2 3 0 0 1 0
0 1 2
5 3 4
1 1 1
1 1 -1
5
請注意輸出最後面是有換行符號的。
3 4 0 0 0 3
2 0 0 9
0 7 8 0
6 0 4 0
1 1 1 0
1 -1 5 0
1 -1 1 0
7
請注意只有休息點需要滿足條件,前往休息點的路途中路過的點不需滿足潮濕度遞增,也不必算入舒適度。
2 2 0 0 1 0
0 0
2 2
1 1
1 1
You are fired!
請注意螃蟹不能直走,也不能走到相同潮濕度的位置休息。
彈塗魚乾事實上是一種餅乾的名稱,大閘蟹應該是不會吃彈塗魚的。