a739:
[橙]質數迷宮
Content
题目描述
思賢是迷宮的狂熱愛好者！在學習質數之後，她決定要設計一個質數迷宮。
注意質數的定義是指在大於1的自然數中，除了1和該數自身外，無法被其他自然數整除的數。
迷宮包含R個橫行及C個直列，而每個格子中都含有一個數，由1開始到 R×C。更清晰地，格子(r,c) 包含着 (r-1)×C+c 這個數。
思賢想令這個迷宮變得更為複雜！所以她決定要把含有質數的格子設為障礙（不能通過）來建構這個迷宮。下方是一個迷宮的例子。
上圖中的障礙以塗黑色的格子來表示。
我們認為兩個格子是相鄰的，當且僅當兩個格子有一條公共邊。即是對於 格子 (r,c), 格子 (r,c-1)，(r,c+1)，(r-1,c) 和 (r+1,c) 都是與它相鄰的。
在迷宮中，每一步你都可以移到與當前格子相鄰且非障礙的格子中。上例中藍線表示一條使用最少步數由 (1,1) 走向 (5,8) 的路徑，而這個步數是 13。
由於思賢是這一方面的專家，所以她想要解決更大的迷宮。但是，畫出如此大的迷宮太花費力氣了。所以她來尋求你的幫忙。那麼，對於 R×C 的質數迷宮，要從起點 (1,1) 到達終點 (R,C)，最少的步數是多少呢？
Input
本題有多個測試用例。輸入的第一行是一個 整數 T (1 ≤ T ≤ 106)，表示測試用例的數量。而對於每個測試用例：僅有一行兩個 整數 R 和 C ( 1 ≤ R ≤ 231-1 , 1 ≤ C ≤ 20 )。
Output
對於每個測試用例，輸出一行一個整數表示從起點到終點最少的步數。若路徑不存在，輸出“-1”。
Sample Input
#1
2 2 2 5 8
Sample Output
#1
-1 13
測資資訊：
記憶體限制：
64
MB
不公開 測資點#0 (10%): 1.0s , <1K
不公開 測資點#1 (10%): 1.0s , <1K
不公開 測資點#2 (10%): 1.0s , <1M
不公開 測資點#3 (10%): 1.0s , <1M
不公開 測資點#4 (10%): 1.0s , <10M
不公開 測資點#5 (10%): 1.0s , <10M
不公開 測資點#6 (10%): 1.0s , <10M
不公開 測資點#7 (10%): 1.0s , <50M
不公開 測資點#8 (10%): 1.0s , <50M
不公開 測資點#9 (10%): 1.0s , <50M
不公開 測資點#0 (10%): 1.0s , <1K
不公開 測資點#1 (10%): 1.0s , <1K
不公開 測資點#2 (10%): 1.0s , <1M
不公開 測資點#3 (10%): 1.0s , <1M
不公開 測資點#4 (10%): 1.0s , <10M
不公開 測資點#5 (10%): 1.0s , <10M
不公開 測資點#6 (10%): 1.0s , <10M
不公開 測資點#7 (10%): 1.0s , <50M
不公開 測資點#8 (10%): 1.0s , <50M
不公開 測資點#9 (10%): 1.0s , <50M
Hint ：
解釋及說明
樣例中第二個測試用例對應的迷宮如題目描述中所述，最少的步數為13。
Tags:
| ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |
|||||