Description
[40%]
One day, a zombie virus outbreak in your city.
To survive, you need to migrate to another safe city.
However, you can only traverse one city to another via roads,
otherwise safety can not be guaranteed.
Also, to minimize the risk during your trip, you wish
to minimize the distanse of your path.
Now, given a map with N cities with M roads.
Find the minimum possible distance between you and your destination.
Assume Roads are bidirection (that is, if there is a road between city A and B.
You can go either from A to B or from B to A.) and all with distance 1.
Hint: BFS
Input
There will be several test cases. Input will terminate with an EOF.
Each test case contains several lines.
First line contains four integer S, E, N, M. Denoting your starting city number,
your destination city number, total number of cities and total number of roads.
For the next M lines, each lines contains two integer A, B. Which means there
is a road between city number A and city number B.
Cities are numbered from 1 to N.
Assume there will be no duplicate roads.
2<=N<=1000, S!=E
0<=M<=N^2
Output
For each test case, output a line with the minimum possible distance between you and your destination.
If it is impossible to get to your desitination city, output -1.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
[50%]
In this problem, you need to implement a BST with following operations :
1. Insert x : Insert x into BST
2. Traverse : Print the preorder traversal order of the BST in one line, each number is separated by a space. If BST is empty, outputs "empty" instead.
3. Bigger x : Given x, output the smallest number which is bigger than x in BST. (x always esxists in BST). If the number doesn't exist, outputs "none" instead.
4. Smaller x : Given x, output the largest number which is smaller than x in BST. (x always exists in BST) If the number doesn't exist, outputs "none" instead.
Input
There are only one test case, and the input will terminate with an EOF.
In the test case, there will be several operations (no more than 10000).
Each operation occupies a line, which is one of the four operations described in the problem statement.
All numbers are positive and not greater than 1000000000.
No duplicated number will be inserted into BST.
Assume the BST is empty at initial.
Output
For "Traverse", "Smaller x", "Bigger x" operation, outputs one line.
The content is described in the problem description.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Each chessboard has numbers in the range 0 to 99 written on each square and is supplied with n chess queens. The task is to place the n queens on the chess board in such a way that no queen threatens another one, and so that the sum of the numbers on the squares selected is the maximum . (For those unfamiliar with the rules of chess, this implies that each row and column of the board contains exactly one queen, and each diagonal contains no more than one queen.)
Write a program that will read in the number and details of the chessboards and determine the highest scores possible for each board under these conditions.
Input
Input will consist of K (the number of boards), on a line by itself, followed by K sets of 64 numbers, each set containts an integer 1<=n<=8, followed by n lines of n numbers. Each number will be a non-negative integer less than 100. There will never be more than 20 boards.
Output
The outputs of all test cases should be printed in order. For each test case a line, print the highest score. If there is no case such that we can choose n queens, print '-1'