1.带分数
#include <iostream>
using namespace std;
int x = 0, number = 0, count = 0;
//交换a,b两数
void Swap(int &a,int &b)
{
int temp=a;
a=b;
b=temp;
}
//将数组区间转化为数字
int getNum(int list[], int f, int r)
{
int i = 0, num = 0;
for (i = f; i <= r; i++)
num = list[i] + num * 10;
return num;
}
void Prim(int list[], int k, int m)
{
if(k==m-1)
{
int a = 0, b = 0, c = 0, bLast = 0;
for (int i = 0; i < x; i++)
{
a = getNum(list, 0, i);
bLast=((number-a)*list[8])%10;
for (int j =i+(8-i)/2; j < 8; j++)
{
if(list[j]==bLast)
{
b = getNum(list, i+1, j);
c = getNum(list, j+1, 8);
if (b % c == 0 && a + b / c == number)
{
++count;
}
break;
}
}
}
}
else
{
for(int i=k;i<m;i++)
{
Swap(list[k],list[i]);
Prim(list,k+1,m);
Swap(list[k],list[i]);
}
}
}
//主函数
int main()
{
int list[] = {1,2,3,4,5,6,7,8,9};
cin>>number;
int temp = number;
while (temp != 0)
{
++x;
temp /= 10;
}
Prim(list,0,9);
cout<<count;
return 0;
}
2.李白喝酒
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int a[15]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,2,2,2,2,2};//-1遇花，2遇店
int n = 0;//记录总数
do{
int sum = 2; //初始斗酒数
for(int i=0; i<15; i++){
if(a[i] == -1){
sum += a[i];
}else{
sum *= a[i];
}
}
if(a[14]==-1&&sum==0){ //a[14]最后一次是遇花
n +=1;
}
}while(next_permutation(a,a+15));//全排列
cout<< n << endl;
return 0;
}
3.第39级台阶
#include <iostream>
using namespace std;
int num=0;//方案数
void fun(int n,int step)
//n表示有多少台阶数 ，step表示步数
{
if(n<0)
return;
if(n==0)
{
if(step%2==0) num++;
return;
}
fun(n-1,step+1);
fun(n-2,step+1);
}
int main()
{
fun(39,0);
cout<<num<<endl;
}
4.穿越雷区
#include <iostream>
using namespace std;
char graph[105][105];
bool visited[105][105];
int sx, sy, ex, ey;
int n;
int minStep = 0x3FFFFFFF;
void dfs(int x, int y, int cnt, char pre) {
if (cnt >= minStep) return;
if (x < 0 || x >= n || y < 0 || y >= n) return;
if (visited[x][y]) return;
if (graph[x][y] != pre) {
visited[x][y] = true;
if (x == ex && y == ey) {
minStep = min(minStep, cnt);
return;
}
dfs(x + 1, y, cnt + 1, graph[x][y]);
dfs(x - 1, y, cnt + 1, graph[x][y]);
dfs(x, y + 1, cnt + 1, graph[x][y]);
dfs(x, y - 1, cnt + 1, graph[x][y]);
visited[x][y] = false;
}
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> graph[i][j];
// 输入的同时记录起始点和终点坐标
if (graph[i][j] == 'A') sx = i, sy = j;
if (graph[i][j] == 'B') ex = i, ey = j;
}
}
dfs(sx, sy, 0, 'T');
if (minStep != 0x3FFFFFFF) {
cout << minStep - 2;
} else {
cout << -1;
}
return 0;
}
5.迷宫
#include <iostream>
#include <string>
#include <queue>
using namespace std;
int maze[35][55];
int dir[][2] = { { 1, 0 }, { 0, -1 }, { 0, 1 }, { -1, 0 } };
char d[4] = { 'D', 'L', 'R', 'U' };
int cnt = 0x3f3f3f3f;
bool vis[35][55];
struct node{
int x;
int y;
string rode;
int step;
node(int xx, int yy, string ss, int tt)
{
x = xx;
y = yy;
rode = ss;
step = tt;
}
};
bool check(int x, int y){
if (x <= 30 && x >= 1 && y <= 50 && y >= 1){
return true;
}
return false;
}
void bfs(int x, int y, string s, int num){
queue<node> q;
q.push(node(x, y, s, num));
while (!q.empty()){
node now = q.front();
q.pop();
vis[now.x][now.y] = true;
if (now.x == 30 && now.y == 50){
if (now.step < cnt){
cnt = now.step;
cout << now.step << endl;
cout<< now.rode << endl;
vis[now.x][now.y] = false;
}
continue;
}
for (int i = 0; i < 4; i++){
int tx = now.x + dir[i][0];
int ty = now.y + dir[i][1];
if (maze[tx][ty] == 0 && !vis[tx][ty] && check(tx, ty)){
q.push(node(tx, ty, now.rode + d[i], now.step + 1));
}
}
}
}
int main(){
for (int i = 1; i <= 30; i++){
for (int j = 1; j <= 50; j++){
maze[i][j] = getchar()-'0';
}
getchar();
}
bfs(1, 1, "", 0);
return 0;
}
6.跳马
#include<iostream>
#include<queue>
using namespace std;
const int X[8] = {-2,-2,-1,-1,1,1,2,2};
const int Y[8] = {-1,1,-2,2,-2,2,-1,1};
int board[9][9];
struct Coordinate{
int x,y,p;
Coordinate(int x,int y,int p):x(x),y(y),p(p){}
};
queue<Coordinate> q;
void bfs(){
Coordinate t = q.front();
q.pop();
for(int i=0;i<8;i++){
int tx = t.x + X[i];
int ty = t.y + Y[i];
if(tx<1||tx>8||ty<1||ty>8||board[tx][ty])continue;
board[tx][ty] = t.p + 1;
q.push(Coordinate(tx,ty,board[tx][ty]));
}
}
int main(){
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
board[x1][y1] = 1;
q.push(Coordinate(x1,y1,1));
bfs();
cout<<board[x2][y2]-1<<endl;
return 0;
}
7.路径之谜
#include<iostream>
using namespace std;
const int X[4] = {1,-1,0,0};
const int Y[4] = {0,0,1,-1};
int n,a[21],b[21];
bool bo[21][21];
int st[401],p=0;
bool dfs(int x,int y){
if(!a[y]||!b[x])return false;
a[y]--,b[x]--;
if(x==n&&y==n){
bool bo = true;
for(int i=1;i<=n;i++)if(a[i]||b[i])bo = false;
if(bo){
st[p++] = (x-1)*n+y-1;
return true;
}
}
for(int i=0;i<4;i++){
int tx = x + X[i];
int ty = y + Y[i];
if(tx<1||tx>n||ty<1||ty>n)continue;
if(dfs(tx,ty)){
st[p++] = (x-1)*n+y-1;
return true;
}
}
a[y]++,b[x]++;
return false;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)cin>>b[i];
dfs(1,1);
cout<<0;
for(int i=p-2;i>=0;i--)cout<<' '<<st[i];
return 0;
}
8.未名湖边的烦恼
#include<iostream>
using namespace std;
int fun(int n,int m)
{
if(n<m) return 0;
if(m==0) return 1;
return fun(n-1,m)+fun(n,m-1);
}
int main()
{
int n,m;
cin>>n>>m;
cout<<fun(n,m)<<endl;
return 0;
}
9.大臣的旅费
10.2n 皇后问题
