h561: pE. 間諜(spy)
Tags : Hamiltonian cycle brute force ore theorem random 時間剪枝 構造
Accepted rate : 3人/4人 ( 75% ) [非即時]
評分方式:
Special

最近更新 : 2022-08-28 20:38

Content

完整題目:https://drive.google.com/file/d/1RSq17g00V-ygkC8x37iLhtNteoqLAwZg/view?usp=sharing

給你一個$n \times m$的方形格子,選擇任意一個點為起點開始走,每次可以選擇走到另外任意一個點,只要新到的那個點不在上一個點的同行、同列或同對角線(簡單來說就是西洋棋皇后的範圍)。請你從起點開始,中間不能走到重複的格子,最後回到起點,輸出一個遍歷所有點的解(注意:必須在最後再輸出一次起點座標),因為解法可能很多,所以輸出任意一種即可。

另外注意這題當初只給$0.3$秒,考慮Judge差異以及其他語言常數差異給$\text{0.5s}$。

限制:

$2 ≤ n, m ≤ 1000$

$n \times m ≤ 2000$

Input

輸入只有兩個數$n$、$m$。

Output

輸出$n \times m$行代表你的解遍歷的順序,每行輸出兩個數代表座標,您可以輸出任何符合的解,請記得在最後再輸出一次起點的座標。另外無解只需輸出$-1$。

Sample Input #1
3 3 
Sample Output #1
-1
Sample Input #2
4 3
Sample Output #2
4 2
2 1
3 3
1 2
3 1
4 3
2 2
4 1
1 3
3 2
1 1
2 3
4 2
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (6%): 0.5s , <1K
公開 測資點#1 (6%): 0.5s , <1K
公開 測資點#2 (6%): 0.5s , <1K
公開 測資點#3 (6%): 0.5s , <1K
公開 測資點#4 (6%): 0.5s , <1K
公開 測資點#5 (7%): 0.5s , <1K
公開 測資點#6 (7%): 0.5s , <1K
公開 測資點#7 (7%): 0.5s , <1K
公開 測資點#8 (7%): 0.5s , <1K
公開 測資點#9 (7%): 0.5s , <1K
公開 測資點#10 (7%): 0.5s , <1K
公開 測資點#11 (7%): 0.5s , <1K
公開 測資點#12 (7%): 0.5s , <1K
公開 測資點#13 (7%): 0.5s , <1K
公開 測資點#14 (7%): 0.5s , <1K
Hint :

注意:這題為special judge,所以上述範例僅為參考用(可能有別的解),只要解法正確即可 $\text{AC}$ !

題目和測資來源:twpca

另外抱歉這裡沒有分subtasks。

如果題目有問題歡迎來信詢問!

Tags:
Hamiltonian cycle brute force ore theorem random 時間剪枝 構造
出處:
TOI入營考2022 [管理者: r1cky(tour1st) ]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」