1（必做） 子集和问题(回溯) * Score 100 已知 n+1 个正数：w i (1≤i≤n) 和 M ，要求找出{w i } 的所有子集使得子集中元素之和等于 M 。解采用大小固定的n-元组(x 1 ,...,x n ) 表达，其中：x i ∈{0，1}，1≤i≤n 。若x i =0 ，表示解集合不包含 w i ；若 x i =1，表示解集合包含 w i 。隐式约束条件是∑ i=1 n w i x i =M。 要求利用回溯方法解决子集和数问题。
输入格式: 第一行为一个正整数 n ，表示总集规模； 第二行是正整数 M ，表示子集的和数； 第三行是总集中 n 个正整数，中间用空格隔开。
输出格式: 如果有答案，则输出所有满足条件的子集（用固定长度n-元组表示符合条件的一个子集，即每行是一个长度为n的0/1序列），按字典序排列。 如果没有答案，则输出 -1
输入样例1: 4 31 11 13 24 7 输出样例1: 0011 1101 输入样例2: 6 30 5 10 12 13 15 18 输出样例2: 001001 101100 110010 数据范围 n≤20,∑w i ,M≤10 9
Bonus 想一想，若只要求判断是否有解，当 n=40 时，有没有在最坏情况下仍能得到答案的算法？
Code Size Limit 16 KB Time Limit 1000 ms Memory Limit 512 MB Stack size limit 8192 KB
2 宝石排列 Score 100 有 n 种形状不同的宝石，每种形状有 n 颗，一共有 n 2 颗宝石。所有宝石一共有 n 种颜色，每种形状的 n 颗宝石颜色均不相同。现在要将这 n 2 颗宝石排成 n 行 n 列的方阵，使得方阵中每一行和每一列中的宝石，都具有 n 种不同的形状和颜色。请设计一个算法，计算对于给定的 n ，有多少种不同的宝石排列方案。
输入格式: 输入 n 值。
输出格式: 输出宝石排列方案的个数。
输入样例: 2 输出样例: 0 数据范围 1≤n≤4
Code Size Limit 16 KB Time Limit 1000 ms Memory Limit 512 MB Stack size limit 8192 KB
3 营救问题(分支限界) Score 100 轮船A在海上遇险，它发出了求救信号。距离最近的轮船B收到了讯息，必须尽快赶到那里。 通过通讯，B获取了一张海洋图。这张图将海洋部分分化成n*n个单位，其中用1 标明的是陆地，用0标明是海洋。船只能从一个格子，移到相邻的四个格子。 为了尽快赶到出事地点A，B最少需要走多远的距离。
输入格式: 第一行为N， 2<N<=1000 第二行到第N+1行是一个N*N的01矩阵，表示海洋地图 最后一行是4个小于N的整数，分别表示哥伦比亚号的行列坐标和铁塔尼号的行列坐标。
输出格式: 哥伦比亚号到铁塔尼号的最短距离，答案精确到整数。
输入样例: 3 001 101 100 1 1 3 3 输出样例: 4 Code Size Limit 16 KB Time Limit 400 ms Memory Limit 64 MB Stack size limit 8192 KB C (gcc)