2. LQDOJ Cup 2025 - Round #2 - Ngôi sao hi vọng
Cuộc thi Chung kết năm của chương trình Đường lên đỉnh Olympia năm \(2035\) đã diễn ra vô cùng kịch tính và hấp dẫn. Các bạn thí sinh lọt vào vòng chung kết đều là những bạn giỏi nhất trong số những bạn giỏi, đã giành được những điểm số vô cùng ấn tượng tại các vòng thi. Tại câu hỏi cuối cùng ở phần thi Về đích, để có cơ hội giành được ngôi vị Quán quân, An đã có một lựa chọn mạo hiểm là đặt ngôi sao hi vọng ở câu hỏi số \(3\) với trị giá \(30\) điểm. Nếu trả lời đúng ở câu này, An sẽ được cộng thêm \(60\) điểm, vừa đủ điểm để vượt qua bạn Bình --- thí sinh đang có số điểm cao nhất và dẫn trước An tận \(55\) điểm. Nếu thành công, An sẽ giành chiến thắng nghẹt thở chỉ với \(5\) điểm cách biệt so với Bình.
Điều đáng nói ở đây, ngoài diễn biến rất gây cấn của cuộc thi với sự cạnh tranh khốc liệt của các thí sinh, là về nội dung và độ khó của câu hỏi mà An nhận được. Đã có nhiều cuộc tranh luận sôi nổi trên diễn đàn LQDOJ --- CLB học sinh chuyên Tin học tại các trường THPT chuyên ở Bà Rịa -- Vũng Tàu, Bình Định, Đà Nẵng, Điện Biên, Khánh Hòa, Ninh Thuận và Quảng Trị. Cộng đồng lập trình thi đấu cho rằng phiên bản tổng quát của câu hỏi trong chương trình có độ khó ngang với Bài 3 của đề thi chọn Học sinh giỏi Quốc gia môn Tin học (VOI). Vậy nội dung câu hỏi như thế nào?
Đề bài như sau:
Cho một mê cung hình chữ nhật được chia làm \(m\) hàng và \(n\) cột. Các hàng của mê cung được đánh số từ \(1\) tới \(m\) theo thứ tự từ dưới lên trên, và các cột được đánh số từ \(1\) tới \(n\) theo thứ tự từ trái sang phải. Ô ở hàng \(i\) và cột \(j\) được ký hiệu là \((i, j)\). Bạn xuất phát ở ô \((1, 1)\) và cần đi tới ô \((m, n)\).
Trong một giây, từ ô \((x,y)\), bạn có thể di chuyển sang một trong bốn ô kề cạnh (là các ô \((x+1, y)\), \((x, y+1)\), \((x-1, y)\) và \((x, y-1)\), nếu như ô đó nằm trong hình chữ nhật).
Tại mỗi thời điểm, mê cung thuộc một trong hai trạng thái là UD hoặc LR. Tùy vào trạng thái của mê cung, bạn có thể di chuyển theo các hướng khác nhau:
- Trạng thái
UDcho phép bạn di chuyển lên trên một ô hoặc xuống dưới một ô (từ \((x,y)\) sang \((x+1,y)\) hoặc \((x-1,y)\)). - Trạng thái
LRcho phép bạn di chuyển sang trái một ô hoặc sang phải một ô (từ \((x,y)\) sang \((x,y-1)\) hoặc \((x,y+1)\)).
Ban đầu, trạng thái của mê cung là UD. Trong bảng hình chữ nhật có \(p\) ô chứa công tắc chuyển đổi trạng thái. Khi đứng tại một trong các ô này, bạn có thể dành ra một giây để nhấn công tắc. Lúc này, trạng thái của mê cung sẽ thay đổi: từ UD sang LR hoặc ngược lại.
Ngoài ra, trong mê cung còn có \(q\) khu vực cấm có dạng hình chữ nhật. Tại mọi thời điểm, bạn không được phép di chuyển vào bất kỳ ô nào trong các khu vực này.
Yêu cầu: Cho trước kích thước của mê cung \(m \times n\), số ô chứa công tắc \(p\), số lượng khu vực cấm \(q\), vị trí của các ô chứa công tắc và phạm vi của mỗi khu vực cấm. Hãy cho biết thời gian ngắn nhất để đi từ ô \((1,1)\) đến ô \((m,n)\) hoặc cho biết không tồn tại cách nào để làm việc này.
Input
Dòng đầu tiên chứa một số nguyên \(\tau\) là số bộ dữ liệu. Tiếp theo là các bộ dữ liệu, mỗi bộ được mô tả theo khuôn dạng sau:
- Dòng đầu tiên là một dòng trống.
- Dòng thứ hai chứa bốn số nguyên \(m, n, p, q\) \((1 \le m,n \le 10^{9}, 1 \le p \le 10^5, 0 \le q \le 10^5)\).
- Trong \(p\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(x_i\) và \(y_i\) \((1 \le x_i \le m, 1 \le y_i \le n)\) thể hiện tọa độ của một ô chứa công thắc. Dữ liệu đảm bảo \(p\) tọa này đôi một phân biệt.
- Trong \(q\) dòng cuối cùng, dòng thứ \(j\) chứa bốn số \(x_1^{(j)}, y_1^{(j)}, x_2^{(j)}, y_2^{(j)}\) \((1 \le x_1^{(j)} \le x_2^{(j)} \le m, 1 \le y_1^{(j)} \le y_2^{(j)} \le n)\) cho biết một khu vực cấm có tọa độ hai góc đối diện là \((x_1^{(j)}, y_1^{(j)})\) và \((x_2^{(j)}, y_2^{(j)})\). Dữ liệu đảm bảo các ô \((1, 1)\) và \((m, n)\) không thuộc bất kỳ khu vực cấm nào.
Gọi \(\Sigma_p\) là tổng giá trị của \(p\) trong các bộ dữ liệu của một test. Tương tự, ta gọi \(\Sigma_q, \Sigma_m, \Sigma_n\) lần lượt là tổng \(q\), tổng \(m\) và tổng \(n\) trong các bộ dữ liệu của bộ test. Dữ liệu đảm bảo \(\Sigma_p, \Sigma_q \le 5 \cdot 10^5\).
Output
Với mỗi bộ dữ liệu, in ra trên một dòng một số nguyên là số giây tối thiểu để đi từ ô \((1,1)\) tới ô \((m,n)\) hoặc \(-1\) nếu không tồn tại cách đi.
Scoring
- Subtask \(1\) (\(14\) điểm): \(m,n \le 2000\); \(\Sigma_m, \Sigma_n \le 10^4\) và \(q \le 10\)
- Subtask \(2\) (\(18\) điểm): \(m,n \le 2000\); \(\Sigma_m, \Sigma_n \le 10^4\)
- Subtask \(3\) (\(14\) điểm): \(p \le 1000; \Sigma_p \le 5000\) và \(q \le 10\)
- Subtask \(4\) (\(18\) điểm): \(p \le 1000; \Sigma_p \le 5000\)
- Subtask \(5\) (\(20\) điểm): \(q \le 10\)
- Subtask \(6\) (\(16\) điểm): Không có ràng buộc gì thêm.
Example
Test 1
Input
2
6 6 9 3
2 6
2 4
6 4
2 2
1 4
6 1
2 1
1 2
1 6
6 5 6 5
1 6 1 6
2 3 3 3
4 4 6 2
2 1
4 1
4 2
1 2
1 4
2 4
2 3 4 3
2 3 2 4Output
18
-1Note
Hai hình vẽ dưới đây lần lượt mô tả hai bộ dữ liệu trong ví dụ ở trên. Các ô màu đỏ là những ô thuộc khu vực cấm. Các ô có biểu tượng màu xanh là những ô chứa công tắc.
Trong bộ dữ liệu thứ nhất:
Phương án di chuyển tối ưu được thể hiện bởi đường màu đen. Trong phương án này, ta cần ấn công tắc \(6\) lần ở các ô \((2, 1)\), \((2, 2)\), \((1, 2)\), \((1, 4)\), \((2, 4)\) và \((2, 6)\). Với số bước di chuyển là \(12\), tổng thời gian cần là \(18\) giây.
Một phương án hợp lệ nhưng không tối ưu được thể hiện bởi đường màu hồng. Phương án này cần \(22\) giây, với thời gian di chuyển là \(18\) và \(4\) lần ấn công tắc ở các ô \((6, 1)\), \((6, 4)\), \((2, 4)\) và \((2, 6)\).
Trong bộ dữ liệu thứ hai: Không tồn tại phương án di chuyển tới ô \((m,n)\).
