admin管理员组

文章数量:821247

2023/1/2总结

一:八皇后 Checker Challenge

题目描述:

一个如下的 6 \times 66×6 的跳棋棋盘,有六个棋子被放置在棋盘上,使得每行、每列有且只有一个,每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。

上面的布局可以用序列 2\ 4\ 6\ 1\ 3\ 52 4 6 1 3 5 来描述,第 ii 个数字表示在第 ii 行的相应位置有一个棋子,如下:

行号 1\ 2\ 3\ 4\ 5\ 61 2 3 4 5 6

列号 2\ 4\ 6\ 1\ 3\ 52 4 6 1 3 5

这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。
并把它们以上面的序列方法输出,解按字典顺序排列。
请输出前 33 个解。最后一行是解的总个数。

输入格式

一行一个正整数 nn,表示棋盘是 n \times nn×n 大小的。

输出格式

前三行为前三个解,每个解的两个数字之间用一个空格隔开。第四行只有一个数字,表示解的总数。

题解:

1:在对角线和行和列都只存在一次,那么利用dfs把每一次的尝试确定下来

#include<stdio.h>
int n,ans=0,a[15],l[27],r[27],cnt[14];//a为列,l为左对角线,r为右对角线,cnt用来记录有可能的路标
void print(int n)
{for(int i=1;i<=n;i++){printf("%d ",cnt[i]);}printf("\n");
}
void dfs(int u)
{if(u>n)//当搜索范围超过边界时输出{ans++;if(ans<=3) print(n);}for(int j=1;j<=n;j++){if(a[j]==0&&l[u+j]==0&&r[u-j+n]==0){a[j]=1;l[u+j]=1;r[u-j+n]=1;cnt[u]=j;dfs(u+1);//标记并寻找下一点a[j]=0;l[u+j]=0;r[u-j+n]=0;cnt[u]=0;//取消标记进行下一次尝试}}
}
int main()
{scanf("%d",&n);dfs(1);//从1开始找printf("%d",ans);
}

 二:马的遍历:

题目描述

有一个 n \times mn×m 的棋盘,在某个点 (x, y)(x,y) 上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步。

输入格式

输入只有一行四个整数,分别为 n, m, x, yn,m,x,y。

输出格式

一个 n \times mn×m 的矩阵,代表马到达某个点最少要走几步(不能到达则输出 -1−1)。

题解:

1:首先了解马怎么走,那么利用int s[8][2]= {2,1,2,-1,-2,1,-2,-1,1,2,-1,2,1,-2,-1,-2};确定马的走向

2:其次了解马到达某个点最少要走几步,就不能用dfs,最优的话就用bfs

3:建立好bfs的框架结构体,队列。

这里学到了一个新知识就是memset:在一段内存块中填充某个给定的值。

#include<stdio.h>
#include<string.h>
struct queue
{int x;int y;
} que[160000];
int n,m;
int mp[410][410];
int b[410][410];
int e(int x,int y)//查看是否超出边界
{if(x<1||x>n||y<1||y>m)return 0;return 1;
}
int s[8][2]= {2,1,2,-1,-2,1,-2,-1,1,2,-1,2,1,-2,-1,-2};//确定方向
void bfs(int x,int y)
{int head=0,tail=1;int sum=0;que[1].x=x;que[1].y=y;b[x][y]=1;mp[x][y]=0;while(head<tail){head++;sum=mp[que[head].x][que[head].y]+1;//成功的点就加一for(int i=0; i<8; i++)//从各个方向遍历{if(e(que[head].x+s[i][0],que[head].y+s[i][1])&&b[que[head].x+s[i][0]][que[head].y+s[i][1]] == 0)//如果没来过便记录{tail++;que[tail].x=que[head].x+s[i][0];que[tail].y=que[head].y+s[i][1];b[que[head].x+s[i][0]][que[head].y+s[i][1]]=1;mp[que[head].x+s[i][0]][que[head].y+s[i][1]]=sum;}}}
}
int main()
{int x,y;scanf("%d %d %d %d",&n,&m,&x,&y);memset(mp,-1,sizeof(mp));bfs(x,y);for(int i=1; i<=n; i++){for(int j=1; j<=m; j++){printf("%-5d",mp[i][j]);}if(i!=n)printf("\n");}return 0;
}

知识点:

今天学习了一下二叉树:

那么它有先序、中序、后序三种遍历

1:先序:二叉树根节点为起点,沿着二叉树外沿,逆时针走一圈回到根节点,路上遇到的元素顺序,就是先序遍历的结果

 2:中序:二叉树每个节点,垂直方向投影下来,然后从左往右数,得出的结果便是中序遍历的结果

 3:后序:围着树的外围绕一圈,如果发现一剪刀就能剪下的葡萄(必须是一颗葡萄)(也就是葡萄要一个一个掉下来,不能一口气掉超过1个这样),就把它剪下来,组成的就是后序遍历了。

 口诀:

先序遍历: 先根 再左 再右

中序遍历: 先左 再根 再右

后序遍历: 先左 再右 再根

本文标签: 202312总结