代码：
#include
int n;//地图大小
char map[10][11];//最大10*10的方阵,还需要一个位置来存储\\0 char touched[10][11];//表示触碰的位置 char result[10][11];//存储结果的数组
int d[8][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};//8个方向 void dfs(int x, int y) {
int i, dx, dy; for(i = 0; i < 8; i++) {
dx = x + d[i][0]; dy = y + d[i][1];
if(dx >= 0 && dx < n && dy >= 0 && dy < n && result[dx][dy] != '.')//如果在地图内 且 不是点 result[dx][dy] = result[dx][dy] + 1;//把累周围的数字累加1 } }
void failure() {
int i, j;
for(i = 0; i < n; i++) for(j = 0; j < n; j++) if(map[i][j] == '*') result[i][j] = '*'; }
void display() {
int i;
for(i = 0; i < n; i++)
printf(\因为前面有行结束标记\\0，所以可以这样输出 }
int main() {
int i, j;//sx, sy, dx, dy分别表示起点坐标和终点坐标 cq表示墙的个数 scanf(\ for(i = 0; i < n; i++) scanf(\ for(i = 0; i < n; i++) {
scanf(\ for(j = 0; j < n; j++) {
if(touched[i][j] == 'x')//如果是触碰过了，就先初始化为0 result[i][j] = '0'; else
result[i][j] = '.'; }
result[i][j + 1] = '\\0';//增加一个行结尾标记 }
//开始搜索
for(i = 0; i < n; i++) {
for(j = 0; j < n; j++)
if(map[i][j] == '*')//如果碰到累，就开始标记周围 dfs(i, j); }
//处理翻出雷的问题 for(i = 0; i < n; i++) for(j = 0; j < n; j++)
if(map[i][j] == '*')//如果碰到累，就开始标记周围 if(touched[i][j] == 'x')//如果累被翻开了 {
failure();
i = n + 1;//用于跳出外面的大循环 break;//跳出当前循环 } display();//输出 return 0; }
5: Additive equations 描述
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. 输入
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. 输出
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 \样例输入 3 3 1 2 3 3 1 2 5 6 1 2 3 5 4 6 样例输出 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 翻译： 描述
我们都知道整数集合是不同整数的集合。现在问题是：给出一个整数集合，你能找出它的所有的相加等式吗？为了解释什么是一个相加等式，让我们来看下面的例子：
1+2=3是集合{1,2,3}的一个相加等式，因为所有的数字都被加到了等式的左手边，也就是1和2，属于相同集合因为他们和是3。我们考虑1+2=3和2+1=3是相同的等式，总是以升序方式输出左手边的数字。因此在这个例子，它声明集合{1,2,3}有唯一一个相加等式 1+2=3。
不保证所有的整数集合都有唯一的相加等式。例如，集合{1,2,5}没有相加等式，集合{1,2,3,5,6}有多个相加等式，像 1+2=3, 1+2+3=6等。当整数集合的数字变大时，最终从我们的思维找到所有的相加等式变得不可能--除非你是John von Neumann才有可能。因此我们需要你去编写一个程序去解决这个问题。 输入
输入数据包括多组测试数据。
第一行包含一个整数N，表示测试组数。
每组测试数据第一行包含一个整数M(1<=M<=30)，代表整数集合中整数的个数，接下来包含M个不同的正整数在同一行。 输出
每组测试数据，你应该输出集合的所有的相加等式。这些等式将会先根据他们的长度被排序，然后根据等式左边数字从左到右的大小进行排序，就像样例输出所展示的。当没有相加等式的时候，简单的输出一行\。每组测试数据后输出一个空行。
思路/方法：注意每组数据输出后还需要一个空的换行。主要是深搜的应用，代码有详细的注释。 代码：
#include
int n, m;//代表组数， 数字个数 int a[30];//存储数字集合
short visited[30];//标识是否被使用过 short flag;//用于表示是否存在加法式子 int sum;//表示当前的和
void dfs(int start, int length) {
int i, j, tempSum = sum;//用个临时变量来代替sum，防止sum被改变 if(length == 0)//用于找式子 {
for(i = start; i < m && tempSum >= a[i]; i++) {
if(tempSum == a[i])//式子和等于集合中一个元素 {
flag = 1;//说明找到了
for(j = 0; j <= i; j++)//开始求出整个式子，肯定是在前i个里面找 {
if(visited[j])//在用过的数字里面找
{
if(tempSum == a[j])//表示输出最后一个加数的情况
printf(\输出格式不一样，所以需要用个if来判断 else
printf(\
tempSum = tempSum - a[j];//输出后就减去，用于判断是否到最后一个了 } } } } }
else//还有长度说明式子还没弄完 {
for(i = start; i < m; i++) {
if(sum + a[i] <= a[m - 1])//数组最后一个是最大值，加的和肯定不能大于它 {
sum = sum + a[i];//不超过就累加上 visited[i] = 1;//标记为使用过 length--;//式子长度减一
dfs(i + 1, length);//搜索下一个位置 //回溯
sum = sum - a[i]; visited[i] = 0; length++; } } } }
int main() {
int i, j; scanf(\ for(i = 0; i < n; i++) {
scanf(\ for(j = 0; j < m; j++) {
scanf(\ visited[j] = 0;//初始化 } flag = 0;
sort(a, a + m);//千万记得排序 for(j = 2; j < m; j++) {
sum = 0;//每次清零
dfs(0, j);//从0位置开始，加法式子长度为j } if(!flag)
printf(\ printf(\每组数据后面要一个空行 }
return 0; }
6: 速算24点 描述
速算24点相信绝大多数人都玩过。就是随机给你四张牌，包括A(1),2,3,4,5,6,7,8,9,10,J(11),Q(12),K(13)。要求只用
'+','-','*','/'运算符以及括号改变运算顺序，使得最终运算结果为24(每个数必须且仅能用一次)。游戏很简单，但遇到无解的情况往往让人很郁闷。你的任务就是针对每一组随机产生的四张牌，判断是否有解。我们另外规定，整个计算过程中都不能出现小数。 输入
每组输入数据占一行，给定四张牌。 输出
每一组输入数据对应一行输出。如果有解则输出\，无解则输出\。 样例输入 A 2 3 6 3 3 8 8 样例输出 Yes No
思路/方法：主要是深搜算法。
4个点的全排列有4!种，而4个数字之间可以有3个位置插入运算符，运算符可以重复，所以一共有4!*4^4种情况，
我们可以每次拿到2个数做运算(+,-,*,/)，得到1个数，再放回原来的集合，那么集合就从4个元素降至3个，减少了一个，就可以用递归处理接下来的同类型的子问题。
注意：当输入10时，一个字符就放不下，所以需要用字符串来存储每个数字，然后转换成数字。
c++代码：
#include
bool dfs(int length) {
int i, j; if(length == 1)
if(a[0] == 24)//判断结果是否为24 return true; else
return false; for(i = 0; i < length; i++) for(j = i + 1; j < length; j++) {
int c = a[i], d = a[j];
a[j] = a[length - 1];//压缩级数，就是经过运算后，集合中的可用数字减少了一个，这里为了方便，把计算结果放在a[i]，把右边未使用的移到a[j]，这样下次用时还是计算a[i]和a[j] //开始四则运算 a[i] = c + d; if(dfs(length - 1)) return true; a[i] = c - d; if(dfs(length - 1)) return true; a[i] = d - c;
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库acm算法经典例题(5)在线全文阅读。
相关推荐：