Graphs算法竞赛入门经典刘汝佳.doc

The GeoSurvComp geologic survey company is responsible for detecting underground oil deposits. GeoSurvComp works with one large rectangular region of land at a time, and creates a grid that divides the land into numerous square plots. It then analyzes each plot separately, using sensing equipment to determine whether or not the plot contains oil.A plot containing oil is called a pocket. If two pockets are adjacent, then they are part of the same oil deposit. Oil deposits can be quite large and may contain numerous pockets. Your job is to determine how many different oil deposits are contained in a grid.InputThe input file contains one or more grids. Each grid begins with a line containingmandn, the number of rows and columns in the grid, separated by a single space. Ifm= 0 it signals the end of the input; otherwiseand. Following this aremlines ofncharacters each (not counting the end-of-line characters). Each character corresponds to one plot, and is either *, representing the absence of oil, or , representing an oil pocket.OutputFor each grid, output the number of distinct oil deposits. Two different pockets are part of the same oil deposit if they are adjacent horizontally, vertically, or diagonally. An oil deposit will not contain more than 100 pockets.Sample Input1 1*3 5*1 8*5 5*0 0Sample Output0122657 - The die is castInterGames is a high-tech startup company that specializes in developing technology that allows users to play games over the Internet. A market analysis has alerted them to the fact that games of chance are pretty popular among their potential customers. Be it Monopoly, ludo or backgammon, most of these games involve throwing dice at some stage of the game.Of course, it would be unreasonable if players were allowed to throw their dice and then enter the result into the computer, since cheating would be way to easy. So, instead, InterGames has decided to supply their users with a camera that takes a picture of the thrown dice, analyzes the picture and then transmits the outcome of the throw automatically.For this they desperately need a program that, given an image containing several dice, determines the numbers of dots on the dice.We make the following assumptions about the input images. The images contain only three dif- ferent pixel values: for the background, the dice and the dots on the dice. We consider two pixelsconnectedif they share an edge - meeting at a corner is not enough. In the figure, pixels A and B are connected, but B and C are not.A setSof pixels is connected if for every pair (a,b) of pixels inS, there is a sequenceinSsuch thata=a1andb=ak, andaiandai+1are connected for.We consider all maximally connected sets consisting solely of non-background pixels to be dice. Maximally connected means that you cannot add any other non-background pixels to the set without making it dis-connected. Likewise we consider every maximal connected set of dot pixels to form a dot.InputThe input consists of pictures of several dice throws. Each picture description starts with a line containing two numbers w and h, the width and height of the picture, respectively. These values satisfy.The followinghlines containwcharacters each. The characters can be: . for a background pixel, * for a pixel of a die, and X for a pixel of a dies dot.Dice may have different sizes and not be entirely square due to optical distortion. The picture will contain at least one die, and the numbers of dots per die is between 1 and 6, inclusive.The input is terminated by a picture starting withw=h= 0, which should not be processed.OutputFor each throw of dice, first output its number. Then output the number of dots on the dice in the picture, sorted in increasing order.Print a blank line after each test case.Sample Input30 15.*.*.*.*X*.*X*.*.*X*.*X*.*.*.*.*.*.*X*.*X*X*.*.*.*X*.*X*X*.*.*.0 0Sample OutputThrow 11 2 2 4784 - Maze ExplorationA maze of rectangular rooms is represented on a two dimensional grid as illustrated in figure 1a. Each point of the grid is represented by a character. The points of room walls are marked by the same character which can be any printable character different than *, _ and space. In figure 1 this character is X. All the other points of the grid are marked by spaces. XXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXX X X X X X X X#X#X#X X X X X X X X#X X X X X X X X X X#X#X#X X X XXXXXX XXX XXXXXXXXXX XXXXXX#XXX#XXXXXXXXXX X X X X X X X X#X#X#X#X X X * X X X#X X X X X X X X X#X#X#X#X XXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXa) Initial maze b) Painted mazeFigure 1. Mazes of rectangular roomsAll rooms of the maze are equal sized with all walls 3 points wide and 1 point thick as illustrated in figure 2. In addition, a wall is shared on its full length by the separated rooms. The rooms can communicate through doors, which are positioned in the middle of walls. There are no outdoor doors. door | XX XX X . X measured from within the room door - .- walls are 3 points wide X . X_ XXXXX | |_ walls are one point thickFigure 2. A room with 3 doorsYour problem is to paint all rooms of a maze which can be visited starting from a given room, called the start room which is marked by a star (*) positioned in the middle of the room. A room can be visited from another room if there is a door on the wall which separates the rooms. By convention, a room is painted if its entire surface, including the doors, is marked by the character # as shown in figure 1b.InputThe program input is a text file structured as follows:1.The first line contains a positive integer which shows the number of mazes to be painted.2.The rest of the file contains the mazes.The lines of the input file can be of different length. The text which represents a maze is terminated by a separation line full of underscores (_). There are at most 30 lines and at most 80 characters in a line for each mazeThe program reads the mazes from the input file, paints them and writes the painted mazes on the standard output.OutputThe output text of a painted maze has the same format as that which has been read for that maze, including the separation lines. The example below illustrates a simple input which contains a single maze and the corresponding output.Sample Input2XXXXXXXXXX X XX * XX X XXXXXXXXXXX XX XX XXXXXX_XXXXXX XX * XX XXXXXX_Sample OutputXXXXXXXXXX#X#XX#XX#X#XXXXXXXXXXX XX XX XXXXXX_XXXXXX#XX#XX#XXXXXX_705 - Slash MazeBy filling a rectangle with slashes (/) and backslashes (), you can generate nice little mazes. Here is an example:As you can see, paths in the maze cannot branch, so the whole maze only contains cyclic paths and paths entering somewhere and leaving somewhere else. We are only interested in the cycles. In our example, there are two of them.Your task is to write a program that counts the cycles and finds the length of the longest one. The length is defined as the number of small squares the cycle consists of (the ones bordered by gray lines in the picture). In this example, the long cycle has length 16 and the short one length 4.InputThe input contains several maze descriptions. Each description begins with one line containing two integerswandh(), the width and the height of the maze. The nexthlines represent the maze itself, and containwcharacters each; all these characters will be either / or .The input is terminated by a test case beginning withw=h= 0. This case should not be processed.OutputFor each maze, first output the line Maze #n:, wherenis the number of the maze. Then, output the line kCycles; the longest has lengthl., wherekis the number of cycles in the maze andlthe length of the longest of the cycles. If the maze does not contain any cycles, output the line There are no cycles.Output a blank line after each test case.Sample Input6 4/3 3/0 0Sample OutputMaze #1:2 Cycles; the longest has length 16.Maze #2:There are no cycles.439 - Knight MovesA friend of you is doing research on theTraveling Knight Problem (TKP)where you are to find the shortest closed tour of knight moves that visits each square of a given set ofnsquares on a chessboard exactly once. He thinks that the most difficult part of the problem is determining the smallest number of knight moves between two given squares and that, once you have accomplished this, finding the tour would be easy.Of course you know that it is vice versa. So you offer him to write a program that solves the difficult part.Your job is to write a program that takes two squaresaandbas input and then determines the number of knight moves on a shortest route fromatob.Input SpecificationThe input file will contain one or more test cases. Each test case consists of one line containing two squares separated by one space. A square is a string consisting of a letter (a-h) representing the column and a digit (1-8) representing the row on the chessboard.Output SpecificationFor each test case, print one line saying To get fromxxtoyytakesnknight moves.Sample Inpute2 e4a1 b2b2 c3a1 h8a1 h7h8 a1b1 c3f6 f6Sample OutputTo get from e2 to e4 takes 2 knight moves.To get from a1 to b2 takes 4 knight moves.To get from b2 to c3 takes 2 knight moves.To get from a1 to h8 takes 6 knight moves.To get from a1 to h7 takes 5 knight moves.To get from h8 to a1 takes 6 knight moves.To get from b1 to c3 takes 1 knight moves.To get from f6 to f6 takes 0 knight moves.532 - Dungeon MasterYou are trapped in a 3D dungeon and need to find the quickest way out! The dungeon is composed of unit cubes which may or may not be filled with rock. It takes one minute to move one unit north, south, east, west, up or down. You cannot move diagonally and the maze is surrounded by solid rock on all sides.Is an escape possible? If yes, how long will it take?Input SpecificationThe input file consists of a number of dungeons. Each dungeon description starts with a line containing three integersL,RandC(all limited to 30 in size).Lis the number of levels making up the dungeon.RandCare the number of rows and columns making up the plan of each level.Then there will followLblocks ofRlines each containingCcharacters. Each character describes one cell of the dungeon. A cell full of rock is indicated by a # and empty cells are represented by a . Your starting position is indicated by S and the exit by the letter E. Theres a single blank line after each level. Input is terminated by three zeroes forL,RandC.Output SpecificationEach maze generates one line of output. If it is possible to reach the exit, print a line of the formEscaped inxminute(s).wherexis replaced by the shortest time it takes to escape.If it is not possible to escape, print the lineTrapped!Sample Input3 4 5S.#.#.#.#.#.#.#E1 3 3S#E#0 0 0Sample OutputEscaped in 11 minute(s).Trapped!10557 - XYZZYProblem D: XYZZYADVENT: /advent/, n.The prototypical computer adventure game, first designed by Will Crowther on the PDP-10 in the mid-1970s as an attempt at computer-refereed fantasy gaming, and expanded into a puzzle-oriented game by Don Woods at Stanford in 1976. (Woods had been one of the authors of INTERCAL.) Now better known as Adventure or Colossal Cave Adventure, but the TOPS-10 operating system permitted only six-letter filenames in uppercase. See also vadding, Zork, and Infocom.It has recently been discovered how to run open-source software on the Y-Crate gaming device. A number of enterprising designers have developedAdvent-style games for deployment on the Y-Crate. Your job is to test a number of these designs to see which are winnable.Each game consists of a set of up to 100 rooms. One of the rooms is thestartand one of the rooms is thefinish. Each room has anenergy valuebetween -100 and +100. One-way doorways interconnect pairs of rooms.The player begins in the start room with 100energy points. She may pass through any doorway that connects the room she is in to another room, thus entering the other room. The energy value of this room is added to the players energy. This process continues until she wins by entering the finish room or dies by running out of energy (or quits in frustration). During her adventure the player may enter the same room several times, receiving its energy each time.The input consists of several test cases. Each test case begins withn, the number of rooms. The rooms are numbered from 1 (the start room) ton(the finish room). Input for thenrooms follows. The input for each room consists of one or more lines containing: the energy value for roomi the number of doorways leaving roomi a list of the rooms that are reachable by the doorways leaving roomiThe start and finish rooms will always have enery level 0.A line containing -1 follows the last test case.In one line for each case, output winnable if it is possible for the player to win, otherwise output hopeless.Sample Input50 1 2-60 1 3-60 1 420 1 50 050 1 220 1 3-60 1 4-60 1 50 050 1 221 1 3-60 1 4-60 1 50 050 1 220 2 1 3-60 1 4-60 1 50 0-1Output for Sample Inputhopelesshopelesswinnablewinnable10047 - The MonocycleA monocycle is a cycle that runs on one wheel and the one we will be considering is a bit more special. It has a solid wheel colored with five different colors as shown in the figure:The colored segments make equal angles (72o) at the center. A monocyclist rides this cycle on angrid of square tiles. The tiles have such size that moving forward from the center of one tile to that of the next one makes the wheel rotate exactly 72oaround its own center. The effect is shown in the above figure. When the wheel is at the center of square 1, the midpoint of the periphery of its blue segment is in touch with the ground. But when the wheel moves forward to the center of the next square (square 2) the midpoint of its white segment touches the ground.Some of the squares of the grid are blocked and hence the cyclist cannot move to them. The cyclist starts from some square and tries to move to a target square in minimum amount of time. From any square either he moves forward to the next square or he remains in the same square but turns 90oleft or right. Each of these actions requires exactly 1 second to execute. He always starts his ride facing north and with the midpoint of the green segment of his wheel touching the ground. In the target square, too, the green segment must be touching the ground but he does not care about the direction he will be facing.Before he starts his ride, please help him find out whether the destination is reachable and if so the minimum amount of time he will require to reach it.InputThe input may contain multiple test cases.The first line of each test case contains two integersMandN(,) giving the dimensions of the grid. Then follows the description of the grid inMlines ofNcharacters each. The character # will indicate a blocked square, all other squares are free. The starting location of the cyclist is marked by S and the target is marked by T. The input terminates with two zeros forMandN.OutputFor each test case in the input first print the test case number on a separate line as shown in the sample output. If the target location can be reached by the cyclist print the minimum amount of time (in seconds) required to reach it exactly in the format shown in the sample output, otherwise, print destination not reachable.Print a blank line between two successive test cases.Sample Input1 3S#T10 10#S.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#T0 0Sample OutputCase #1destination not reachable Case #2minimum time = 49 sec10004 - BicoloringIn 1976 the Four Color Map Theorem was proven with the assistance of a computer. This theorem states that every map can be colored using only four colors, in such a way that no region is colored using the same color as a neighbor region.Here you are asked to solve a simpler similar problem. You have to decide whether a given arbitrary connected graph can be bicolored. That is, if one can assign colors (from a palette of two) to the nodes in such a way that no two adjacent nodes have the same color. To simplify the problem you can assume: no node will have an edge to itself. the graph