Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
8.9 kB
8
Indexable
Never
//Quân mã

Trong một bàn cờ NxM.



Tìm số lần đi tối thiểu để quân mã ăn hết quân địch.



Quân mã có thể di chuyển xung quanh theo 8 hướng .(H1)



H1



Example : test case 1



Quân mã mất 3 lần di chuyển để ăn hết quân địch . (2,3) -> (3,5) -> (4,3)



H2



Input : dòng đầu tiên là số lương test case



            Dòng 2 là kích thước của bàn cờ



Tiếp theo là bàn cờ :



3 là vị trí xuất phát của quân mã



1 là vị trí quân địch



0 là vị trí trống.



Quân mã có thể di chuyển trên tất cả các vị trí trên bàn cờ (0,1,3).



Output:



In ra số lần di chuyển nhỏ nhất để quân mã ăn hết quân địch.



Sample input:



2



5 7



0 0 0 0 0 0 0



0 3 0 0 0 0 0



0 0 0 1 0 0 0



0 0 0 0 0 1 0



0 0 0 1 0 0 0



10 10



1 0 0 0 0 0 0 0 0 0



0 0 0 0 0 0 0 0 0 0



0 0 0 0 0 0 0 0 0 0



0 0 0 0 0 0 0 1 0 0



0 1 0 0 0 0 0 0 0 0



0 0 0 0 0 0 0 0 0 0



0 0 0 0 0 0 3 0 0 0



0 0 0 0 0 0 0 0 0 0



0 0 0 0 0 0 0 0 0 0



0 0 0 0 0 0 0 0 0 1



Sample output:



Case #1



3



Case #2



12













































//Quân tượng
Xét bàn cờ vuông kích thước n×n. Các dòng được đánh số từ 1 đến n, từ dưới lên trên. Các cột được đánh số từ 1 đến n từ trái qua phải.

Ô nằm trên giao của dòng i và cột j được gọi là ô (i,j). Trên bàn cờ có m (0 ≤ m ≤ n) quân cờ. Với m > 0, quân cờ thứ i ở ô (ri, ci), i = 1,2,..., m. Không có hai quân cờ nào ở trên cùng một ô. Trong số các ô còn lại của bàn cờ, tại ô (p, q) có một quân tượng. Mỗi một nước đi, từ vị trí đang đứng quân tượng chỉ có thể di chuyển đến được những ô trên cùng đường chéo với nó mà trên đường đi không phải qua các ô đã có quân

Cần phải đưa quân tượng từ ô xuất phát (p, q) về ô đích (s,t).

Cho kích thước bàn cờ n, số quân cờ hiện có trên bàn cờ m và vị trí của chúng, ô xuất phát và ô đích của quân tượng. Hãy xác định số nước đi ít nhất cần thực hiện để đưa quân tượng về ô đích hoặc đưa ra số -1 nếu điều này không thể thực hiện được.

 

 

Constraints

N = 1~200

 

Input

Dòng đầu tiên chứa số testcase. Mỗi testcase có cấu trúc như sau:

Dòng thứ nhất chứa 6 số nguyên n, m, p, q, s, t.

Nếu m > 0 thì mỗi dòng thứ i trong m dòng tiếp theo chứa một cặp số nguyên ri , ci xác định vị trí quân thứ i.

Hai số liên tiếp trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

 

Output

Với mỗi test case in ra 1 dòng duy nhất là số nước đi tìm được.

 

Sample

 

Input

2

5 5 5 5 5 3
1 2
1 5
2 2
4 2
4 3

8 3 7 2 1 4

5 4

3 4

4 7

 

Output

2

3




































//Crazy King
King Peter lives in kingdom A, and his daughter in kingdom B. King received a letter telling that her daughter gave birth to a child. King is incredibly curious to see his grandchild! Unfortunately that’s not gonna be that easy.
Kingdoms A and B are separated by a forest. There are lots of enemies in the forest, and King is not that curious to see them. If they attack king on his way to kingdom B, then he will never ever see his grandchild and daughter again because of lethal consequences.

Security Council of the King disposes information about location of the enemies, which makes the things easier for king. For some unknown reason a forest is MxN chessboard. (N is the number of rows, and M is the number of columns). N,M <=100 are positive integers.

Enemies of the King can ride horses as showed in the picture. Usually horses ride (or jump) that way in Chess. Unfortunately king can’t take an airplane from point A to point B because it is not invented yet. So he moves the same way as chess-king does (refer to picture for details).   





King can’t move to a square X, if a horse of the enemy is on that square. While the king is moving horses are not, but if at least one horse can reach square X in one move, then king can't move to that square (except for the case when square X is either kingdom A or B).

You are the chief of Electronic Intelligence department of kingdom A (by the way the computers are already invented). And you’re asked to find the length of the shortest route L from kingdom A to

B, as king can’t wait any longer.

Input

The first line of input contains the number of tests T <=100. The first line of each test contains 2 numbers M and N. Then M lines follow each containing N symbols from the set S = { ‘.’, ‘Z’, ‘A’, ‘B’}. ‘.’ means that square is not occupied. ‘Z’ - horse occupies that square. ‘A’ - kingdom A, ‘B’ - kingdom B. Each test contains exactly one kingdom A and B.

Output

Find number L for each test and print line L if King can reach kingdom B. Replace L with corresponding number. If King can’t safely reach the kingdom B print line -1.

Sample

 

Input

4

5 5

.Z..B

..Z..

Z...Z

.Z...

A....

3 2

ZB

.Z

AZ

6 5

....B

.....

.....

..Z..

.....

A..Z.

3 3

ZZ.

...

AB.

 

Output

-1

2

-1

1











































//Nuoc Bien
Trái đất nóng lên kéo theo mực nước biển dâng. Hòn đảo nhỏ Gonnasinka thuê bạn để dự báo trước hiểm họa này. Cho trước 1 lưới tọa độ thể hiện cao độ của đảo, hãy giúp họ tính toán xem nước biển dâng cao bao nhiêu thì hòn đảo sẽ bị chia cắt.

Input

Input gồm nhiều bộ test, mỗi bộ test bao gồm:

Dòng đầu ghi 2 số n, m là chiều dài và chiều rộng.

Sau đó là n dòng, mỗi dòng gồm m số, mỗi số cho biết độ cao của ô đó, giá trị 0 chỉ mực nước biển. Những ô giá trị 0 dọc theo đường viền và những ô số 0 liền kề những ô này chỉ mặt biển. Những ô có giá trị 0 còn lại (được bao bọc bởi các số > 0) là đất liền bên trong đảo nhưng có độ cao ngang mặt nước biển. Hòn đảo lúc đầu chưa bị chia cắt. Số n và m không lớn hơn 100 và độ cao không lớn hơn 1000.

Dòng cuối cùng của input chứa 2 số 0

Output

Với mỗi bộ test, in ra:

Case n: Island splits when ocean raises f feet. (Đảo bị chia khi nước biển dâng cao f feet)

Hoặc

Case n: Island never splits. (Đảo không bao giờ bị chia cắt)

Example

Input:

5 5

3 4 3 0 0

3 5 5 4 3

2 5 4 4 3

1 3 0 0 0

1 2 1 0 0

5 5

5 5 5 5 7

4 1 1 1 4

4 1 2 1 3

7 1 0 0 4

7 3 4 4 4

0 0

Output:

Case 1: Island never splits.

Case 2: Island splits when ocean rises 3 feet.
















































//Đảo Cột
Trong ma trận nhị phân, phép đảo cột của ma trận là việc thay thế các giá trị của cột
đó từ 0 -> 1 và từ 1 -> 0. Cho ma trận nhị phân NxM (N <= 100, M <= 20), hỏi sau K
lần đảo cột thì số hàng gồm toàn số 1 nhiều nhất có thể thu được là bao nhiêu. (Yêu
cầu phải đảo cột đúng K lần và một cột có thể được đảo nhiều lần)
Ví dụ
Với ví dụ bên, nếu K = 1, ta sẽ có kết quả lớn nhất khi đảo cột thứ 2 và thu được 1
hàng gồm toàn số 1 là hàng thứ 4. Nếu K = 2, kết quả thu được là 2 khi đảo cột thứ 2
và cột thứ 3.

 

0

1

0

0

0

1

0

0

1

1

0

0

0

0

0

1

0

1

1

1

1

0

0

1

1

 

K=1, có 1 hàng toàn 1

0

0

0

0

0

1

1

0

1

1

0

1

0

0

0

1

1

1

1

1

 1

1

0

1

1

 

K=2, có 2 hàng toàn 1

0

0

1

0

0

1

1

1

1

1

0

1

1

0

0

1

1

0

1

1

1

1

1

1

1

 

Input: Cho 3 số N, M, K

Tiếp theo là ma trận NxM

Output: In ra số lượng hàng toàn 1 nhiều nhất định dạng như bên dưới

Case #1 1

Case #2 2