ICPC训练联盟暑期线上集训（递归与回溯）

• A POJ 1664 放苹果
• 题解
• B POJ 2013 Symmetric Order
• 题解
• C POJ 3889 Fractal Streets
• D POJ 2083 Fractal
• 题解
• E POJ 1979 Red and Black
• 题解
• F UVA 167 The Sultan\’s Successors
• 题解
• G POJ 2258 The Settlers of Catan
• 题解
• H POJ 1040 Transportation
• I POJ 1315 Don\’t Get Rooked
• J UVA 750 8 Queens Chess Problem

A POJ 1664 放苹果

传送门: link.
Description

把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。

Input

第一行是测试数据的数目t（0 <= t <= 20）。以下每行均包含二个整数M和N，以空格分开。1<=M，N<=10。

Output

对输入的每组数据M和N，用一行输出相应的K。

Sample Input

1
7 3

Sample Output

8

题解

递归，有以下几种情况：
当m = 1，f(1,n) = 1；将一个苹果放在n个盘子里，只有一种放法；

当n = 1，f(m,1) = 1；将m个苹果放在1个盘子里，只有一种方法；

当m = n，f(m,n) = f(m,n-1)+1；每个盘子里都放苹果，或者至少有一个盘子里不放苹果；

当m < n， f(m,n) = f(m,m)；只能把m个苹果放进m个盘子里；

当m > n，f(m,n) = f(m,n-1)+f(m-n,n)；每个盘子里都放苹果，先把n个苹果抽出来放进n个盘子里，剩下m-n个苹果放进n个盘子里；或者至少一个盘子里不放。

#include<stdio.h>int fun(int m,int n){if(m==0||n==1)return 1;if(m<n)return fun(m,m);elsereturn fun(m,n-1)+fun(m-n,n);}int main(){int t,m,n;scanf(\"%d\",&t);while(t--){scanf(\"%d%d\",&m,&n);printf(\"%d\\n\",fun(m,n));}return 0;}

B POJ 2013 Symmetric Order

传送门: link.
Description

In your job at Albatross Circus Management (yes, it’s run by a bunch of clowns), you have just finished writing a program whose output is a list of names in nondescending order by length (so that each name is at least as long as the one preceding it). However, your boss does not like the way the output looks, and instead wants the output to appear more symmetric, with the shorter strings at the top and bottom and the longer strings in the middle. His rule is that each pair of names belongs on opposite ends of the list, and the first name in the pair is always in the top part of the list. In the first example set below, Bo and Pat are the first pair, Jean and Kevin the second pair, etc.

Input

The input consists of one or more sets of strings, followed by a final line containing only the value 0. Each set starts with a line containing an integer, n, which is the number of strings in the set, followed by n strings, one per line, sorted in nondescending order by length. None of the strings contain spaces. There is at least one and no more than 15 strings per set. Each string is at most 25 characters long.

Output

For each input set print “SET n” on a line, where n starts at 1,
followed by the output set as shown in the sample output.

Sample Input

7
Bo
Pat
Jean
Kevin
Claude
William
Marybeth
6
Jim
Ben
Zoe
Joey
Frederick
Annabelle
5
John
Bill
Fran
Stan
Cece
0

Sample Output

SET 1
Bo
Jean
Claude
Marybeth
William
Kevin
Pat
SET 2
Jim
Zoe
Frederick
Annabelle
Joey
Ben
SET 3
John
Fran
Cece
Stan
Bill

题解

递归实现

#include<iostream>using namespace std;void fun(int n){string s;cin>>s;cout<<s<<endl;if(--n){cin>>s;if(--n)fun(n);cout<<s<< endl;}}int main(){int n,cas=1;while(cin>>n&&n){cout<<\"SET \"<<cas++<<endl;fun(n);}return 0;}

不用递归的方法

#include<stdio.h>int main(){char str[100][100];int n,i,head,tail,cas=1;while(~scanf(\"%d\",&n)&&n){head=0;tail=n-1;for(i=0; i<n; i++){if(i%2==0)scanf(\"%s\",str[head++]);elsescanf(\"%s\",str[tail--]);}printf(\"SET %d\\n\",cas++);for(i=0; i<n; i++)printf(\"%s\\n\",str[i]);}return 0;}

C POJ 3889 Fractal Streets

传送门: link.
Description

With a growing desire for modernization in our increasingly larger cities comes a need for new street designs. Chris is one of the unfortunate city planners responsible for these designs. Each year the demands keep increasing, and this year he has even been asked to design a completely new city.
More work is not something Chris needs right now, since like any good bureaucrat, he is extremely lazy. Given that this is a character trait he has in common with most computer scientists it should come as no surprise that one of his closest friends, Paul, is in fact a computer scientist. And it was Paul who suggested the brilliant idea that has made Chris a hero among his peers: Fractal Streets! By using a Hilbert curve, he can easily fill in rectangular plots of arbitrary size with very little work.
A Hilbert curve of order 1 consists of one “cup”. In a Hilbert curve of order 2 that cup is replaced by four smaller but identical cups and three connecting roads. In a Hilbert curve of order 3 those four cups are in turn replaced by four identical but still smaller cups and three connecting roads, etc. At each corner of a cup a driveway (with mailbox) is placed for a house, with a simple successive numbering. The house in the top left corner has number 1, and the distance between two adjacent houses is 10m.
The situation is shown graphically in figure 2. As you can see the Fractal Streets concept successfully eliminates the need for boring street grids, while still requiring very little effort from our bureaucrats.
>As a token of their gratitude, several mayors have offered Chris a house in one of the many new neighborhoods built with his own new scheme. Chris would now like to know which of these offerings will get him a house closest to the local city planning office (of course each of these new neighborhoods has one). Luckily he will not have to actually drive along the street, because his new company “car” is one of those new flying cars. This high-tech vehicle allows him to travel in a straight line from his driveway to the driveway of his new office. Can you write a program to determine the distance he will have to fly for each offier (excluding the vertical distance at takeoff and landing)?

Input

On the first line of the input is a positive integer, the number of test cases. Then for each test case:
A line containing a three positive integers, n < 16 and h, o < 231, specifying the order of the Hilbert curve, and the house numbers of the offered house and the local city planning office.

Output

For each test case:
One line containing the distance Chris will have to fly to his work in meters, rounded to the nearest integer.

Sample Input

3
1 1 2
2 16 1
3 4 33

Sample Output

10
30
50

D POJ 2083 Fractal

传送门: link.
Description

A fractal is an object or quantity that displays self-similarity, in a somewhat technical sense, on all scales. The object need not exhibit exactly the same structure at all scales, but the same “type” of structures must appear on all scales.
A box fractal is defined as below :
A box fractal of degree 1 is simply
X
A box fractal of degree 2 is
X X
X
X X
If using B(n – 1) to represent the box fractal of degree n – 1, then a box fractal of degree n is defined recursively as following
B(n – 1) B(n – 1)
B(n – 1)
B(n – 1) B(n – 1)
Your task is to draw a box fractal of degree n.

Input

The input consists of several test cases. Each line of the input contains a positive integer n which is no greater than 7. The last line of input is a negative integer −1 indicating the end of input.

Output

For each test case, output the box fractal using the ‘X’ notation. Please notice that ‘X’ is an uppercase letter. Print a line with only a single dash after each test case.

Sample Input

1
2
3
4
-1

Sample Output

题解

递归画图。

#include<stdio.h>#include<math.h>#include<string.h>char a[2500][2500];int N,i,j,len,n,m;void dfs(int x,int y,int cur){if(cur==1){a[x][y]=\'X\';return;}dfs(x,y,cur-1);//左上角m=x;n=y+pow(3,cur-2)*2;dfs(m,n,cur-1);//右上角m=x+pow(3,cur-2)*2;n=y;dfs(m,n,cur-1);//左下角m=x+pow(3,cur-2)*2;n=y+pow(3,cur-2)*2;dfs(m,n,cur-1);//右下角m=x+pow(3,cur-2);n=y+pow(3,cur-2);dfs(m,n,cur-1);//中间}int main(){while(~scanf(\"%d\",&N)){if(N==-1)break;len=pow(3,N-1);for(i=0; i<len; i++){for(j=0; j<len; j++)a[i][j]=\' \';a[i][len]=\'\\0\';}dfs(0,0,N);for(i=0; i<len; i++){printf(\"%s\\n\",a[i]);}printf(\"-\\n\");}return 0;}

E POJ 1979 Red and Black

传送门: link.
Description

There is a rectangular room, covered with square tiles. Each tile is colored either red or black. A man is standing on a black tile. From a tile, he can move to one of four adjacent tiles. But he can’t move on red tiles, he can move only on black tiles.
Write a program to count the number of black tiles which he can reach by repeating the moves described above.

Input

The input consists of multiple data sets. A data set starts with a line containing two positive integers W and H; W and H are the numbers of tiles in the x- and y- directions, respectively. W and H are not more than 20.
There are H more lines in the data set, each of which includes W characters. Each character represents the color of a tile as follows.
‘.’ – a black tile
‘#’ – a red tile
‘@’ – a man on a black tile(appears exactly once in a data set)
The end of the input is indicated by a line consisting of two zeros.

Output

For each data set, your program should output a line which contains the number of tiles he can reach from the initial tile (including itself).

Sample Input

6 9
…#.
…#
…
…
…
…
…
#@…#
.#…#.
11 9
.#…
.#.#######.
.#.#…#.
.#.#.###.#.
.#.#…@#.#.
.#.#####.#.
.#…#.
.#########.
…
11 6
…#…#…#…
…#…#…#…
…#…#…###
…#…#…#@.
…#…#…#…
…#…#…#…
7 7
…#.#…
…#.#…
###.###
…@…
###.###
…#.#…
…#.#…
0 0

Sample Output

45
59
6
13

题解

求一个人可以走的最多黑色块数，先找到这个人的位置，然后从上下左右四个方向走，#符号相当于墙，无法走。题目可以转换为求连通块的最多个数。

#include<stdio.h>#include<string.h>char s[50][50];int n,m;int dfs(int x,int y){if(x<0||x>n-1||y<0||y>m-1)return 0;if(s[x][y]==\'#\'){return 0;}else{s[x][y]=\'#\';return 1+dfs(x+1,y)+dfs(x-1,y)+dfs(x,y+1)+dfs(x,y-1);}}int main(){int i,j,sum;while(~scanf(\"%d%d\",&m,&n)){if(m==0&&n==0)break;for(i=0; i<n; i++){scanf(\"%s\",s[i]);}sum=0;for(i=0; i<n; i++){for(j=0; j<m; j++){if(s[i][j]==\'@\'){sum=dfs(i,j);}}}printf(\"%d\\n\",sum);}return 0;}

F UVA 167 The Sultan’s Successors

传送门: link.

The Sultan of Nubia has no children, so she has decided that the country will be split into up to k
separate parts on her death and each part will be inherited by whoever performs best at some test. It
is possible for any individual to inherit more than one or indeed all of the portions. To ensure that
only highly intelligent people eventually become her successors, the Sultan has devised an ingenious
test. In a large hall filled with the splash of fountains and the delicate scent of incense have been
placed k chessboards. Each chessboard has numbers in the range 1 to 99 written on each square and is
supplied with 8 jewelled chess queens. The task facing each potential successor is to place the 8 queens
on the chess board in such a way that no queen threatens another one, and so that the numbers on
the squares thus selected sum to a number at least as high as one already chosen by the Sultan. (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.)
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. (You know that the Sultan is both a
good chess player and a good mathematician and you suspect that her score is the best attainable.)

Input

Input will consist of k (the number of boards), on a line by itself, followed by k sets of 64 numbers,
each set consisting of eight lines of eight numbers. Each number will be a positive integer less than100. There will never be more than 20 boards.

Output

Output will consist of k numbers consisting of your k scores, each score on a line by itself and right
justified in a field 5 characters wide.

Sample Input

1
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
48 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64

Sample Output

260

题解

全排列问题，标记皇后位置， 每次判断vis【0】【i】第i列 和vis【1】【i+cnt】 副对角线上和vis【2】【i-cnt+8】 主对角线上是否存在皇后。

#include<stdio.h>#include<string.h>int map[10][10];int v[3][40];int n,i,j,k,max;void dfs(int cnt, int sum){if(cnt>=8){if(max<sum)max=sum;}else{for(int i=0; i<8; i++){if(!v[0][i]&&!v[1][i+cnt]&&!v[2][i-cnt+8]){v[0][i] = v[1][i+cnt] = v[2][i-cnt+8]=1;dfs(cnt+1, sum+map[cnt][i]);v[0][i] = v[1][i+cnt] = v[2][i-cnt+8]=0;}}}}int main(){scanf(\"%d\",&n);while(n--){memset(map, 0, sizeof(map));memset(v, 0, sizeof(v));max=0;for(i=0; i<8; i++)for(j=0; j<8; j++)scanf(\"%d\",&map[i][j]);dfs(0,0);printf(\"%5d\\n\",max);}return 0;}

G POJ 2258 The Settlers of Catan

传送门: link.
Description

Within Settlers of Catan, the 1995 German game of the year, players attempt to dominate an island by building roads, settlements and cities across its uncharted wilderness.
You are employed by a software company that just has decided to develop a computer version of this game, and you are chosen to implement one of the game’s special rules:
When the game ends, the player who built the longest road gains two extra victory points.
The problem here is that the players usually build complex road networks and not just one linear path. Therefore, determining the longest road is not trivial (although human players usually see it immediately).
Compared to the original game, we will solve a simplified problem here: You are given a set of nodes (cities) and a set of edges (road segments) of length 1 connecting the nodes.
The longest road is defined as the longest path within the network that doesn’t use an edge twice. Nodes may be visited more than once, though.
Example: The following network contains a road of length 12.
o o–o o
\\ / \\ /
o–o o–o
/ \\ /
o o–o o–o
\\ /
o–o

Input

The input will contain one or more test cases.
The first line of each test case contains two integers: the number of nodes n (2<=n<=25) and the number of edges m (1<=m<=25). The next m lines describe the m edges. Each edge is given by the numbers of the two nodes connected by it. Nodes are numbered from 0 to n-1. Edges are undirected. Nodes have degrees of three or less. The network is not neccessarily connected.
Input will be terminated by two values of 0 for n and m.

Output

For each test case, print the length of the longest road on a single line.

Sample Input

3 2
0 1
1 2
15 16
0 2
1 2
2 3
3 4
3 5
4 6
5 7
6 8
7 8
7 9
8 10
9 11
10 12
11 12
10 13
12 14
0 0

Sample Output

2
12

题解

枚举每个点搜索找最长路。

#include<stdio.h>#include<string.h>#define max(a,b) a>b?a:bint n,m,u,v,ans;int maps[33][33];int vis[33][33];void dfs(int node,int road){for(int i=0; i<n; i++){if(!maps[node][i]||!maps[i][node])continue;if(vis[node][i]||vis[i][node])continue;vis[node][i]=vis[i][node]=1;road++;ans=max(road,ans);dfs(i,road);vis[node][i]=vis[i][node]=0;road--;}}int main(){while(~scanf(\"%d%d\",&n,&m)&&n+m){memset(maps,0,sizeof(maps));ans=0;for(int i=0; i<m; i++){scanf(\"%d%d\",&u,&v);maps[u][v]=maps[v][u]=1;}for(int i=0; i<n; i++){memset(vis,0,sizeof(vis));dfs(i,0);}printf(\"%d\\n\",ans);}return 0;}

H POJ 1040 Transportation

传送门: link.
Description

Ruratania is just entering capitalism and is establishing new enterprising activities in many fields in- cluding transport. The transportation company TransRuratania is starting a new express train from city A to city B with several stops in the stations on the way. The stations are successively numbered, city A station has number 0, city B station number m. The company runs an experiment in order to improve passenger transportation capacity and thus to increase its earnings. The train has a maximum capacity n passengers. The price of the train ticket is equal to the number of stops (stations) between the starting station and the destination station (including the destination station). Before the train starts its route from the city A, ticket orders are collected from all onroute stations. The ticket order from the station S means all reservations of tickets from S to a fixed destination station. In case the company cannot accept all orders because of the passenger capacity limitations, its rejection policy is that it either completely accept or completely reject single orders from single stations.
Write a program which for the given list of orders from single stations on the way from A to B determines the biggest possible total earning of the TransRuratania company. The earning from one accepted order is the product of the number of passengers included in the order and the price of their train tickets. The total earning is the sum of the earnings from all accepted orders.

Input

The input file is divided into blocks. The first line in each block contains three integers: passenger capacity n of the train, the number of the city B station and the number of ticket orders from all stations. The next lines contain the ticket orders. Each ticket order consists of three integers: starting station, destination station, number of passengers. In one block there can be maximum 22 orders. The number of the city B station will be at most 7. The block where all three numbers in the first line are equal to zero denotes the end of the input file.

Output

The output file consists of lines corresponding to the blocks of the input file except the terminating block. Each such line contains the biggest possible total earning.

Sample Input

10 3 4
0 2 1
1 3 5
1 2 7
2 3 10
10 5 4
3 5 10
2 4 9
0 2 5
2 5 8
0 0 0

Sample Output

19
34

I POJ 1315 Don’t Get Rooked

传送门: link.

Description

In chess, the rook is a piece that can move any number of squares vertically or horizontally. In this problem we will consider small chess boards (at most 4×4) that can also contain walls through which rooks cannot move. The goal is to place as many rooks on a board as possible so that no two can capture each other. A configuration of rooks is legal provided that no two rooks are on the same horizontal row or vertical column unless there is at least one wall separating them.
The following image shows five pictures of the same board. The first picture is the empty board, the second and third pictures show legal configurations, and the fourth and fifth pictures show illegal configurations. For this board, the maximum number of rooks in a legal configuration is 5; the second picture shows one way to do it, but there are several other ways.

Your task is to write a program that, given a description of a board, calculates the maximum number of rooks that can be placed on the board in a legal configuration.

Input

The input contains one or more board descriptions, followed by a line containing the number 0 that signals the end of the file. Each board description begins with a line containing a positive integer n that is the size of the board; n will be at most 4. The next n lines each describe one row of the board, with a ‘.’ indicating an open space and an uppercase ‘X’ indicating a wall. There are no spaces in the input.

Output

For each test case, output one line containing the maximum number of rooks that can be placed on the board in a legal configuration.

Sample Input

4
.X…
…
XX…
…
2
XX
.X
3
.X.
X.X
.X.
3
…
.XX
.XX
4
…
…
…
…
0

Sample Output

5
1
5
2
4

J UVA 750 8 Queens Chess Problem

传送门: link.