a742: 福州地铁
標籤 : 图论
通過比率 : 93% (13 人 / 14 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2013-08-10 22:41

內容

福州开建地铁了,但建成之前带来的只是不便而已。小海豚去上学,可是修地铁的路段不能通行只能绕路了。

上图就是 (0,0)-(0,1),(0,1)-(3,1),(0,3)-(3,3),(3,3)-(3,4),(1,1)-(1,3),(2,1)-(2,3) 都开挖地铁的结果。小海豚上学只能走粗线的路了。

輸入說明

首先一行是7个数字:N, M, X0, Y0, X1, Y1, K

福州市南北向的长度为 N,东西向的长度为 M。 N,M<=1000。小海豚家的坐标是 (X0,Y0),学校的坐标是 (X1,Y1)。0 <= X0, Y0, X1, Y1 < N。K (0 <= K <= 100)表示以下K行数据,

以下K行格式为:X2,Y2,X3,Y3。表示从(X2,Y2)到(X3,Y3)修地铁,不能通行(注意通过该坐标的其他方向仍可能通行)。测资保证X2==X3或Y2==Y3,且X2<=X3,Y2<=Y3。

多笔测资,EOF结束。下面范例中的第二笔测资,就是上面的图表示的。

 

 

輸出說明

每笔输出从家到学校的最短路程长度,如果不能到达就输出 10080 (一星期的分钟数)

 

範例輸入
4 3 2 2 1 0 0 
4 5 0 0 3 4 6
0 0 0 1
0 1 3 1
0 3 3 3
3 3 3 4
1 1 1 3
2 1 2 3
9 9 8 8 1 3 2
8 7 8 8
7 8 8 8
範例輸出
3
13
10080
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (60%): 1.0s , <1K
公開 測資點#1 (10%): 1.0s , <1K
公開 測資點#2 (10%): 1.0s , <1K
公開 測資點#3 (10%): 1.0s , <1K
公開 測資點#4 (10%): 1.0s , <1K
提示 :
標籤:
图论
出處:
海豚原创 [編輯:
htbb (海豚爸爸)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」