ZOJ上BFS问题

<++++++++++++++++++++DEPTH FIRST SEARCH PROBLEMS ON ZOJ++++++++++++++++++++> ZOJ Problem Set – 1004:Anagrams by Stack Time Limit: 1 Second      Memory Limit: 32768 KB How can anagrams result from sequences of stack operations? There are two sequences of stack operators which can convert TROT to TORT: [ i i i i o o o o i o i i o o i o ] where i stands for Push and o stands for Pop. Your program should, given pairs of words produce sequences of stack operations which convert the first word to the second. Input The input will consist of several lines of input. The first line of each pair of input lines is to be considered as a source word (which does not include the end-of-line character). The second line (again, not including the end-of-line character) of each pair is a target word. The end of input is marked by end of file. Output For each input pair, your program should produce a sorted list of valid sequences of i and o which produce the target word from the source word. Each list should be delimited by [ ] and the sequences should be printed in "dictionary order". Within each sequence, each i and o is followed by a single space and each sequence is terminated by a new line. Process A stack is a data storage and retrieval structure permitting two operations: Push - to insert an item and Pop - to retrieve the most recently pushed item We will use the symbol i (in) for push and o (out) for pop operations for an initially empty stack of characters. Given an input word, some sequences of push and pop operations are valid in that every character of the word is both pushed and popped, and furthermore, no attempt is ever made to pop the empty stack. For example, if the word FOO is input, then the sequence: i i o i o o is valid, but i i o is not (it's too short), neither is i i o o o i (there's an illegal pop of an empty stack)     Valid sequences yield rearrangements of the letters in an input word. For example, the input word FOO and the sequence i i o i o o produce the anagram OOF. So also would the sequence i i i o o o. You are to write a program to input pairs of words and output all the valid sequences of i and o which will produce the second member of each pair from the first. Sample Input madam adamm bahama bahama long short eric rice Sample Output [ i i i i o o o i o o i i i i o o o o i o i i o i o i o i o o i i o i o i o o i o ] [ i o i i i o o i i o o o i o i i i o o o i o i o i o i o i o i i i o o o i o i o i o i o i o i o ] [ ] [ i i o i o i o o ] Source: Zhejiang University Local Contest 2001 ZOJ Problem Set – 1204:Additive equations Time Limit: 10 Seconds      Memory Limit: 32768 KB We all understand that an integer set is a collection of distinct integers. Now the question is: given an integer set, can you find all its addtive equations? To explain what an additive equation is, let's look at the following examples: 1+2=3 is an additive equation of the set {1,2,3}, since all the numbers that are summed up in the left-hand-side of the equation, namely 1 and 2, belong to the same set as their sum 3 does. We consider 1+2=3 and 2+1=3 the same equation, and will always output the numbers on the left-hand-side of the equation in ascending order. Therefore in this example, it is claimed that the set {1,2,3} has an unique additive equation 1+2=3. It is not guaranteed that any integer set has its only additive equation. For example, the set {1,2,5} has no addtive equation and the set {1,2,3,5,6} has more than one additive equations such as 1+2=3, 1+2+3=6, etc. When the number of integers in a set gets large, it will eventually become impossible to find all the additive equations from the top of our minds -- unless you are John von Neumann maybe. So we need you to program the computer to solve this problem. Input The input data consists of several test cases. The first line of the input will contain an integer N, which is the number of test cases. Each test case will first contain an integer M (1<=M<=30), which is the number of integers in the set, and then is followed by M distinct positive integers in the same line. Output For each test case, you are supposed to output all the additive equations of the set. These equations will be sorted according to their lengths first( i.e, the number of integer being summed), and then the equations with the same length will be sorted according to the numbers from left to right, just like the sample output shows. When there is no such equation, simply output "Can't find any equations." in a line. Print a blank line after each test case. Sample Input 3 3 1 2 3 3 1 2 5 6 1 2 3 5 4 6 Output for the Sample Input 1+2=3 Can't find any equations. 1+2=3 1+3=4 1+4=5 1+5=6 2+3=5 2+4=6 1+2+3=6 Source: Zhejiang University Local Contest 2002, Preliminary ZOJ Problem Set – 1984:Genetic Code Time Limit: 5 Seconds      Memory Limit: 32768 KB      Special Judge The connections between mathematics and biology are complicated. Most of the time they do not run along nice-looking links that merrily join at first glance, but they are abstract and not always easily established. Lake Vostok - about 14000 square kilometers large, up to 650 meters deep, and covered by 3743 meters of ice - was recently discovered on the Antarctic continent. The lake remained under conditions of high pressure and no sunlight for several millions of years. It is believed that ordinary life has evolved to a more efficient form using a genetic code composed of only three bases (the current state of ignorance proclaims the four bases adenine, cytosine, guanine, and thymine). Until reasonable names are found, the three bases will be abbreviated as N, O, and P. Moreover, the genome is single-stranded and directed, i.e., we may see it as a sequence over the alphabet {N,O,P}. Unless risking instability, it is necessary that the genome is a Thue-sequence, due to the Norwegian mathematician A. Thue (1863-1922). Define a subsegment of a sequence to be a connected subsequence, and call two subsegments adjacent if one follows immediately after the other in the sequence. A Thue-sequence is a sequence where no adjacent subsegments are equal. For example, NOPNO is and NOPNPNO is not a Thue-sequence, so that the first may be a genome whereas the second may not. To be able to simulate experiments with the new genomes, you are asked to generate genomes of certain lengths. Input The input contains several test cases. Each test case consists of an integer n. You may assume that 1<=n<=5000. The last test case is followed by a zero. Output For each test case specified by n output on a single line any genome of length n. If no genome of length n exists, output a blank line instead. Sample Input 1 2 10 20 0 Sample Output N NO NONPNOPNPO NONPNOPNPONOPNONPNOP Source: University of Ulm Local Contest 2003 ZOJ Problem Set – 1457:Prime Ring Problem Time Limit: 10 Seconds      Memory Limit: 32768 KB A ring is compose of n circles as shown in diagram. Put natural number 1, 2, ..., n into each circle separately, and the sum of numbers in two adjacent circles should be a prime. Note: the number of first circle should always be 1. Input n (0 < n < 20) Output The output format is shown as sample below. Each row represents a series of circle numbers in the ring beginning from 1 clockwisely and anticlockwisely. The order of numbers must satisfy the above requirements. Print solutions in lexicographical order. You are to write a program that completes above process. Print a blank line after each case. Sample Input 6 8 Sample Output Case 1: 1 4 3 2 5 6 1 6 5 2 3 4 Case 2: 1 2 3 8 5 6 7 4 1 2 5 8 3 4 7 6 1 4 7 6 5 8 3 2 1 6 7 4 3 8 5 2 Source: Asia 1996, Shanghai (Mainland China) ZOJ Problem Set – 1008:Gnome Tetravex Time Limit: 10 Seconds      Memory Limit: 32768 KB Hart is engaged in playing an interesting game, Gnome Tetravex, these days. In the game, at the beginning, the player is given n*n squares. Each square is divided into four triangles marked four numbers (range from 0 to 9). In a square, the triangles are the left triangle, the top triangle, the right triangle and the bottom triangle. For example, Fig. 1 shows the initial state of 2*2 squares. Fig. 1 The initial state with 2*2 squares The player is required to move the squares to the termination state. In the termination state, any two adjoining squares should make the adjacent triangle marked with the same number. Fig. 2 shows one of the termination states of the above example. Fig. 2 One termination state of the above example It seems the game is not so hard. But indeed, Hart is not accomplished in the game. He can finish the easiest game successfully. When facing with a more complex game, he can find no way out. One day, when Hart was playing a very complex game, he cried out, "The computer is making a goose of me. It's impossible to solve it." To such a poor player, the best way to help him is to tell him whether the game could be solved. If he is told the game is unsolvable, he needn't waste so much time on it. Input The input file consists of several game cases. The first line of each game case contains one integer n, 0 <= n <= 5, indicating the size of the game. The following n*n lines describe the marking number of these triangles. Each line consists of four integers, which in order represent the top triangle, the right triangle, the bottom triangle and the left triangle of one square. After the last game case, the integer 0 indicates the termination of the input data set. Output You should make the decision whether the game case could be solved. For each game case, print the game number, a colon, and a white space, then display your judgment. If the game is solvable, print the string "Possible". Otherwise, please print "Impossible" to indicate that there's no way to solve the problem. Print a blank line between each game case. Note: Any unwanted blank lines or white spaces are unacceptable. Sample Input 2 5 9 1 4 4 4 5 6 6 8 5 4 0 4 4 3 2 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 0 Output for the Sample Input Game 1: Possible Game 2: Impossible Source: Asia 2001, Shanghai (Mainland China) ZOJ Problem Set – 1411:Anniversary Time Limit: 10 Seconds      Memory Limit: 32768 KB Nahid Khaleh decides to invite the kids of the "Shahr-e Ghashang" to her wedding anniversary. She wants to prepare a square-shaped chocolate cake with known size. She asks each invited person to determine the size of the piece of cake that he/she wants (which should also be square-shaped). She knows that Mr. Kavoosi would not bear any wasting of the cake. She wants to know whether she can make a square cake with that size that serves everybody exactly with the requested size, and without any waste. Input The first line of the input file contains a single integer t (1 <= t <= 10), the number of test cases, followed by input data for each test case. Each test case consist of a single line containing an integer s, the side of the cake, followed by an integer n (1 <= n <= 16), the number of cake pieces, followed by n integers (in the range 1...10) specifying the side of each piece. Output There should be one output line per test case containing one of the words KHOOOOB! or HUTUTU! depending on whether the cake can be cut into pieces of specified size without any waste or not. Sample Input 2 4 8 1 1 1 1 1 3 1 1 5 6 3 3 2 1 1 1 Sample Output KHOOOOB! HUTUTU! Source: Asia 2002, Tehran (Iran), Iran Domestic ZOJ Problem Set – 1482:Partitions Time Limit: 10 Seconds      Memory Limit: 1024 KB Given a maze, you are to tell the number of partitions in it. Input The first line is an integer N (2 <= N <= 3000), the size of the maze. The next N lines each has N 0-and-1's, 1 for an obstacle and 0 for an unoccupied space. Two unoccupied spaces are in the same partition if: 1. They are adjacent (above, below, left/right to,but not diagonally), or 2. They are both connected with another unoccupied space. Output One number on a line - the number of partitions. Sample Input 2 0 1 1 0 Sample Output 2 Author: PAN, Minghao Source: ZOJ Monthly, January 2003 ZOJ Problem Set – 1267:Mapping the Route Time Limit: 1 Second      Memory Limit: 32768 KB Finding a path through a maze is a popular problem for computers. In this problem, a maze will consist of a rectangular array of square cells, each of which may have walls on the north, south, east and/or west sides of the cell. One cell will be identified as the starting point, and another will be identified as the goal. Your task is to find the unique route from the starting point to the goal, label each cell in the path with its sequence in the path, identify the cells that were visited but that were not in the path, and display the maze. The algorithm you use to find a path through the maze must be the one described below. Imagine a robot is positioned in the starting cell. The robot first attempts to go west from that cell, then north, then east, then south, in sequence. The robot can move in the selected direction if (a) there is no wall preventing it from moving in that direction, and (b) it has not yet been in the next cell in that direction. When the robot reaches the goal, its trip is over. If the robot reaches a cell at which no further progress is possible, it retreats to the previous cell it occupied and attempts to move in the next untried direction. Consider the simple maze shown on the left below. It is two cells high and three cells wide. The starting cell is labeled `S' and the goal cell is labeled `G'. When the robot starts, it would first try to move west (left), but finds a wall. It then tries to move north (up), and is again blocked by a wall. A wall also prevents it from moving east (right), so it finally tries to move south (down), and succeeds. From the new cell it will eventually move east. Here it repeats its movement algorithm. Although no wall blocks its potential westward movement, it has already 'visited' the cell in that direction, so it next tries to move north, and is successful. Unfortunately, after moving north, it finds no way to extend its path, and so it retreats to the previously occupied cell. Now it tries to move east, and is successful. From that cell it will move north, and there it finds the goal. The maze that would be displayed on the output is shown on the right below. Note that the starting cell is labeled `1', each cell in the path to the goal (including the one containing the goal) is labeled with its sequence number, and each cell that was visited but is not in the path is labeled with question marks. +---+---+---+        +---+---+---+ | S |  | G |        |  1|???|  5| +  +  +  +        +  +  +  + |          |        |  2  3  4| +---+---+---+        +---+---+---+ Input View the maze as an array of cells, with the northernmost row being row 1, and the westernmost column being column 1. In the maze above, the starting cell is row 1, column 1, and the goal cell is row 1, column 3. There will be one or more mazes to process in the input. For each maze there will first appear six integers. The first two give the height (number of rows) and width (numer of columns) of the maze (in cells). The next two give the position (row and column number) of the starting cell, and the last two give the position of the goal. No maze will have more than 12 rows or 12 columns, and there will always be a path from the starting point to the goal.