1.迷宫：给定一个 N×M 方格的迷宫，迷宫里有T处障碍，障碍处不可通过。给定起点坐标和终点坐标，问: 每个方格最多经过1次，有多少种从起点坐标到终点坐标的方案。在迷宫中移动有上、下、左、右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。
入：输入的第一行包含三个整数N、M和T (1≤N,M≤5,0≤T<N*M)，其中 N 代表行数，M 代表列数，T 代表障碍总数。
第二行起点坐标SX、SY (1≤SX≤N,1≤SY≤M)，终点坐标FX、FY (1≤FX≤N,1≤FY≤M) 。
接下来T行，每行为障碍点的坐标X, Y (1≤X≤N,1≤Y≤M) 。
出：输出仅一个整数，表示从起点坐标到终点坐标的方案总数。
入：2 2 1 1 1 2 2 1 2 出：1
#include<iostream>
#include<cstdlib>
#include<string>
using namespace std;
int shuzu1[6][6];
bool shuzu2[6][6];
int dx[4]={0,0,1,-1}; int dy[4]={-1,1,0,0}; int t,n,m,x,y,sum,fx,fy,sx,sy;
void hanshu(int x,int y);
int main(){
cin>>n>>m>>t;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
shuzu1[i][j]=1;
}
}
cin>>sx>>sy>>fx>>fy;
for(int i=1;i<=t;i++){
cin>>x>>y;
shuzu1[x][y]=0;
}
hanshu(sx,sy);
cout<<sum;
return 0;
}
void hanshu(int x,int y){
if(x==fx && y==fy){
sum++;
return;
}
else{
for(int i=0;i<=3;i++){
if(shuzu2[x+dx[i]][y+dy[i]]==0 && shuzu1[x+dx[i]][y+dy[i]]==1){
shuzu2[x][y]=1;
hanshu(x+dx[i],y+dy[i]);
shuzu2[x][y]=0;
}
}
}
}
2.自然数的拆分问题：任何一个大于 1 的自然数 n ，总可以拆分成若干个小于 n 的自然数之和。现在给你一个自然数 n ，要求你将 n 拆分成一些数字的和。每个拆分后的序列中的数字从小到大排序。然后你需要输出这些序列，其中字典序小的序列需要优先输出。
入：输入一个整数 n（1 <= n <= 8），表示需要拆分的自然数。
出：输出若干个的加法式子。
入：7 出：1+1+1+1+1+1+1 1+1+1+1+1+2 …….. 3+4
#include<iostream>
#include<cstdlib>
#include<string>
using namespace std;
int shuzu1[9];
int n;
void out(int a){
for(int i=0;i<a;i++){
if(i==0){
cout<<shuzu1[i];
}else{
cout<<"+"<<shuzu1[i];
}
}
cout<<endl;
return;
}
void fx1(int a,int b,int c){//从a开始选择
//b是总和,c是从c+1开始选择
if(a==n){
return;
}
if(b==n){
out(c);
return;
}
for(int i=a;i<=n-b;i++){
shuzu1[c]=i;//选择了什么数
fx1(i,b+i,c+1);
}
}
int main(){
while(cin>>n){
fx1(1,0,0);
}
return 0;
}
3.选数：已知 n 个整数 x1, x2, · · ·,xn，以及 1个整数 k（k < n）。从 n 个整数中任选 k 个整数相加，可分别得到一系列的和。例如当 n = 4，k = 3，4 个整数分别为 3, 7, 12, 19 时，可得全部的组合与它们的和为：3 + 7 + 12 = 22
3 + 7 + 19 = 29 7 + 12 + 19 = 38 3 + 12 + 19 = 34
现在，要求你计算出和为素数共有多少种。例如上例，只有一种的和为素数：3 + 7 + 19 = 29。
入：第一行两个空格隔开的整数 n, k, (1≤n≤20,k<n)。第二行 n 个整数，分别为 x1,x2,· · · ,xn (1≤xi≤5×106)。
出：输出一个整数，表示种类数。
入：4 3 3 7 12 10 出：1
#include<iostream>
#include<cstdlib>
#include<string>
using namespace std;
int n,k,temp,sum;int shuzu1[20];
int fx1(int a) {
for(int i=2; i<a; i++) {
if(a%i==0) {
return 0;
}
}
return 1;
}
void fx2(int a,int b) {
if(a==0) {
temp+=fx1(sum);
} else {
b++;
for(int i=b; i<=n; i++) {
sum+=shuzu1[i];
a--;
fx2(a,i);
sum-=shuzu1[i];
a++;
}
}
}
int main() {
cin>>n>>k;
for(int i=1; i<=n; i++) {
cin>>shuzu1[i];
}
fx2(k,0);
cout<<temp;
return 0;
}
4.好奇诡的游戏：这个游戏类似象棋，但是只有黑白马各一匹，在点 x1, y1 和 x2, y2 上。它们得从点 x1, y1 和 x2, y2 走到 (1,1) 。这个游戏与普通象棋不同的地方是：马可以走“日”，也可以像象走“田”。现在想知道两匹马到 (1,1) 的最少步数，你能解决这个问题么？
入：第1行：两个整数x1, y1 第2行：两个整数x2, y2 (1≤x1,y1,x2,y2≤20)
出：第1行：黑马到(1,1)的步数 第2行：白马到(1,1)的步数 假设棋盘为20*20
入：12 16 18 10 出：8 9
#include<iostream>
#include<string>
#include<cstring>
#include<queue>
using namespace std;
class point{
public:
int x,y;
};
int n=20; int dx[]={2,2,2,2,1,1,-1,-1,-2,-2,-2,-2};
int dy[]={-2,-1,1,2,-2,2,-2,2,-2,-1,1,2}; int x1,y1,x2,y2,temp1,temp2;
int x,y; int x_temp,y_temp; int shuzu1[22][22];
bool shuzu2[22][22];
queue<point> q;
int fx1(int a,int b){
memset(shuzu2,false,sizeof(shuzu2));
memset(shuzu1,false,sizeof(shuzu1));
while(!q.empty()){
q.pop();
}
q.push((point){a,b});
shuzu2[a][b]=true;
while(!q.empty()){
x=q.front().x;
y=q.front().y;
q.pop();
if(x+y==2){
return shuzu1[1][1];
}
for(int i=0;i<12;i++){
x_temp=x+dx[i];
y_temp=y+dy[i];
if(x_temp<=0 || x_temp>n || y_temp<=0 || y_temp>n){
continue;
}
if(shuzu2[x_temp][y_temp]==true){
continue;
}
shuzu1[x_temp][y_temp]=shuzu1[x][y]+1;
shuzu2[x_temp][y_temp]=true;
q.push((point){x_temp,y_temp});
}
}
}
int main(){
cin>>x1>>y1>>x2>>y2;
temp1=fx1(x1,y1);temp2=fx1(x2,y2);
cout<<temp1<<endl;cout<<temp2<<endl;
return 0;
}
5.N皇后问题：规定当两个皇后出现在同一行，同一列，或者同一条对角线上时，它们会互相攻击。 现在要在一个 N×N 的棋盘上放置 N 个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，请问有多少种放置方法。
入：包含多组测试数据。 每组数据输入一行，仅包含一个整数 N （1 <= N <= 13）。
出：每组数据输出一行，包含一个整数，表示放置方案总数。
入：8 6 13 出：92 4 73712
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
int n,sum;int shuzu1[500];
bool shuzu2[500];
void fx1(int m,int n) {
if(m==n) {
sum++;
return;
}
for(int i=0; i<n; i++) {
if(!shuzu2[i]){
continue;
}
bool temp = true;
for(int j=0; j<m; j++) {
if(shuzu1[j]==i){
continue;
}
if(abs(m-j)==abs(shuzu1[j]-i)) {
temp= false;
break;
}
}
if(temp) {
shuzu1[m] = i;
shuzu2[i] = false;
fx1(m+1,n);
shuzu2[i] = true;
}
}
}
int main() {
while(cin >> n) {
sum=0;
memset(shuzu1,0,sizeof(shuzu1));
memset(shuzu2,1,sizeof(shuzu2));
fx1(0,n);
cout<<sum<<endl;
}
return 0;
}
6.吃奶酪：房间里放着 n 块奶酪。一只小老鼠要把它们都吃掉，问至少要跑多少距离？老鼠一开始在 (0,0)点处。
入：第一行有一个整数，表示奶酪的数量 n。
第 2 到第 (n+1) 行，每行两个实数，第 (i+1) 行的实数分别表示第 i 块奶酪的横纵坐标 xi, yi。
对于全部的测试点，保证 1 ≤ n ≤ 15, |xi|, |yi| ≤ 200，小数点后最多有 3位数字。
出：输出一行一个实数，表示要跑的最少距离，保留 2 位小数。
入：4 1 1 1 -1 -1 1 -1 -1 出：7.41
#include<iostream>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
int n;
double shuzu1[17], shuzu2[17]; double dp[17][1 << 17];
const int MAX = 2e9;
int fx1(int a, int b) {
return a & (1 << b);
}
int fx2(int a, int b) {
return a & (~(1 << b));
}
double suan(double x1, double y1, double x2, double y2) {
return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
void dfs(int a, int b) {
if (dp[a][b] != -1) {
return;
}
dp[a][b] = MAX;
for (int i = 0; i < n; ++i) {
if (i == a) {
continue;
}
if (!fx1(b, i)) {
continue;
}
dfs(i, fx2(b, a));
dp[a][b] = min(dp[a][b], dp[i][fx2(b, a)] + suan(shuzu1[i], shuzu2[i], shuzu1[a], shuzu2[a]));
}
}
int main() {
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> shuzu1[i] >> shuzu2[i];
}
for (int i = 0; i < n; ++i) {
for (int j = 1; j < (1 << n); ++j) {
dp[i][j] = -1;
}
}
for (int i = 0; i < n; ++i) {
dp[i][1 << i] = suan(0, 0, shuzu1[i], shuzu2[i]);
}
for (int i = 0; i < n; ++i) {
dfs(i, (1 << n) - 1);
}
double sum = MAX;
for (int i = 0; i < n; ++i) {
sum = min(sum, dp[i][(1 << n) - 1]);
}
printf("%.2f\n",sum);
return 0;
}