ITK24_ĐỒ THỊ CƠ BẢN

Một khu vườn hình chữ nhật có kích thước \(NxM\) (\(N\) dòng, \(M\) cột). Ta đánh số các dòng từ \(1\) đến \(N\) theo chiều từ trên xuống dưới và các cột từ \(1\) đến \(M\) theo chiều từ trái sang phải để chia khu vườn thành các ô. Trong các ô đó, ngoài những ô là đất để người nông dân trồng rau vẫn có những ô là đá không thể trồng rau được. Một chú ốc sên xuất phát tại ô \((x, y)\) (\(x\) là vị trí dòng, \(y\) là vị trí cột). Nếu ô xuất phát là đất, chú ốc sên có thể di chuyển sang \(4\) ô kề cạnh với ô đó (bên trái, bên phải, bên trên, bên dưới) và đương nhiên không thể di chuyển vào ô đá được. Trường hợp ô xuất phát là đá thì chú ốc sên không thể di chuyển đến ô nào khác.

Yêu cầu: Hãy tính xem chú ốc sên có thể di chuyển đến nhiều nhất là bao nhiêu ô để ăn rau?

Dữ liệu vào:

• Dòng thứ nhất gồm \(4\) số nguyên \(N, M, X, Y\) (mỗi số cách nhau một khoảng trắng)
  \((1 ≤ X ≤ N ≤ 2000, 1 ≤ Y ≤ M ≤ 2000);\)
• Trong \(N\) dòng tiếp theo, mỗi dòng gồm \(M\) số nguyên \(0\) hoặc \(1\) (mỗi số cách nhau một khoảng trắng). Số \(0\) nghĩa là ô trồng rau, số \(1\) nghĩa là ô đá.

Dữ liệu ra:

• Gồm một số nguyên là số lượng ô lớn nhất mà chú ốc sên có thể di chuyển đến để ăn rau. Nếu chú ốc sên không ăn được ô rau nào thì ghi kết quả là \(-1\).

Ví dụ:

Input:

4 5 2 4
0 0 1 0 0
0 1 0 0 1
1 0 0 0 0
0 1 0 0 1

Output:

10

• Sub1: Có 50% test tương ứng 50% số điểm của bài với \(N, M < 10;\)
• Sub2: Có 30% test tương ứng 30% số điểm của bài với \(N, M ≤ 100;\)
• Sub3: Có 20% test khác tương ứng 20% số điểm còn lại của bài với \(N, M ≤ 2x10^3.\)

Cho đồ thị vô hướng \(G = (V, E)\) gồm \(n\) đỉnh và \(m\) cạnh, các đỉnh được đánh số từ \(1\) tới \(n\) và các cạnh được đánh số từ \(1\) tới \(m\).

Độ dài của mỗi cạnh có giá trị là \(1\). Một đồ thị sẽ có \(1\) nút trung tâm \(s\).

Với mỗi đỉnh có thể tới được từ đỉnh \(s\), tính khoảng cách ngắn nhất từ đỉnh đó tới \(S\) và in ra các đỉnh theo thứ tự khoảng cách ngắn nhất tăng dần.

Lưu ý : Nếu \(2\) đỉnh có khoảng cách bằng nhau thì nhãn nào nhỏ hơn sẽ đứng trước.

Input

• Dòng đầu gồm 3 số nguyên \(n, m, s\) \((n, m \leq 10^5, 1 \leq s \leq n)\)
• \(m\) dòng sau mỗi dòng gồm hai số \(u\), \(v\) thể hiện hai đầu của một cạnh.

Output

• In ra số dòng tương ứng với số đỉnh có thể tới được từ \(s\) theo thứ tự khoảng cách ngắn nhất tăng dần.
• Trên mỗi dòng in ra nhãn của đỉnh đó và khoảng cách ngắn nhất của đỉnh đó tới \(s\).

Sample Input

7 6 1
1 2
2 3
3 4
4 5
5 6
1 3

Sample Output

1 0
2 1
3 1
4 2
5 3
6 4

Đường hầm dài nhất
Các nhà khảo sát địa chất đã ghi lại độ sâu tối đa ứng với các vị trí có thể đào được mà không gặp mạch nước ngầm của một khu đất có dạng hình chữ nhật. Các số đo được ghi lại trên một bản đồ gọi là bản đồ độ sâu. Bản đồ độ sâu là một hình chữ nhật được chia thành \(MxN\) ô vuông, mỗi ô vuông ghi một số nguyên biểu thị độ sâu có thể đào được tại vị trí đó của khu đất. Người ta muốn đào một đường hầm thoát nước dài nhất của khu đất này bắt đầu từ một ô có độ sâu nào đó (không nhất thiết bắt đầu ở các ô biên) và kết thúc ở một ô tùy ý. Do nước chảy từ nơi cao xuống nơi thấp, nên đường hầm thoát nước khi đào qua các ô phải theo nguyên tắc đi từ ô có độ sâu nhỏ hơn đến ô chung cạnh có độ sâu lớn hơn.

Yêu cầu:
Hãy đưa ra độ dài tối đa của đường hầm thoát nước có thể đào được.

Input

• Dòng đầu ghi hai số nguyên \(M và N ( 0< M \le 100; 0 < N \le 100)\).
• M dòng tiếp theo, mỗi dòng ghi \(N\) số nguyên \(a_i\)
  \((0< ai \le 100, i = 1,..,N)\).

Output

• gồm một số nguyên là số ô mà đường hầm dài nhất đi qua.
  Ví dụ:

Input:

3   4  
10  21  3   7
11  31  12  14
5   21  13  16

Output:

5