2022.01.14学习总结

归纳总结：每次学习后，提炼关键点进行总结。 #生活技巧# #学习技巧# #知识复习法#

今天刷到任务量了，松了一口气，让我们来看看今天刷的题目吧。

昨天晚上做了填涂颜色。

题目描述

由数字00组成的方阵中，有一任意形状闭合圈，闭合圈由数字11构成，围圈时只走上下左右44个方向。现要求把闭合圈内的所有空间都填写成22.例如：6 \times 66×6的方阵（n=6n=6），涂色前和涂色后的方阵如下：

0 0 0 0 0 0

0 0 1 1 1 1

0 1 1 0 0 1

1 1 0 0 0 1

1 0 0 0 0 1

1 1 1 1 1 1

0 0 0 0 0 0

0 0 1 1 1 1

0 1 1 2 2 1

1 1 2 2 2 1

1 2 2 2 2 1

1 1 1 1 1 1

输入格式

每组测试数据第一行一个整数n(1 \le n \le 30)n(1≤n≤30)

接下来nn行，由00和11组成的n \times nn×n的方阵。

方阵内只有一个闭合圈，圈内至少有一个00。

//感谢黄小U饮品指出本题数据和数据格式不一样. 已修改(输入格式)

输出格式

已经填好数字22的完整方阵。

输入输出样例

输入 #1复制

6 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 1 1 1 1 1 1

输出 #1复制

0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 2 2 1 1 1 2 2 2 1 1 2 2 2 2 1 1 1 1 1 1 1

说明/提示

1 \le n \le 301≤n≤30

思路

我们可以先用dfs找出所有没有被圈住的0并将其染色，然后剩下的0则为被围住的部分，将其染成2即可。

并且为了方便找出所有未被圈住的0，我们可以在方阵外圈一层0，从（0，0）为起点开始搜索，这样即可找出所有未被圈主的0。

代码

#include<stdio.h>

int n,mp[35][35];

int next[4][2]={1,0,-1,0,0,1,0,-1};//下一步

void dfs(int x,int y)//当前位置

{

if(x<0||x>n+1||y<0||y>n+1||mp[x][y]!=0){//不符合条件，返回

return;

}

else{

for(int i=0;i<4;i++){//四种路径展开

int tx=x+next[i][0];

int ty=y+next[i][1];

dfs(tx,ty);

mp[x][y]=3;//标记没有被圈住的0为3

}

}

}

int main()

{

scanf("%d",&n);

for(int i=1;i<=n;i++){

for(int j=1;j<=n;j++){

scanf("%d",&mp[i][j]);

}

}

/*for(int i=1;i<=n;i++){

for(int j=1;j<=n;j++){

if(mp[i][j]==0){

dfs(i,j);

}

}

}*/

dfs(0,0);//起点从（0，0）开始

for(int i=1;i<=n;i++){

for(int j=1;j<=n;j++){

if(mp[i][j]==0){

mp[i][j]=2;//剩余的0则为被圈住的0，进行染色

}

}

}

for(int i=1;i<=n;i++){

for(int j=1;j<=n;j++){

if(mp[i][j]==3){

mp[i][j]=0;//恢复没有被圈住的0

}}}

for(int i=1;i<=n;i++){//输出

for(int j=1;j<=n;j++){

printf("%d ",mp[i][j]);

}printf("\n");

}

}

今天上午做了找水坑那个题。

题目描述

Due to recent rains, water has pooled in various places in Farmer John's field, which is represented by a rectangle of N x M (1 <= N <= 100; 1 <= M <= 100) squares. Each square contains either water ('W') or dry land ('.'). Farmer John would like to figure out how many ponds have formed in his field. A pond is a connected set of squares with water in them, where a square is considered adjacent to all eight of its neighbors. Given a diagram of Farmer John's field, determine how many ponds he has.

由于近期的降雨，雨水汇集在农民约翰的田地不同的地方。我们用一个NxM(1<=N<=100;1<=M<=100)网格图表示。每个网格中有水('W') 或是旱地('.')。一个网格与其周围的八个网格相连，而一组相连的网格视为一个水坑。约翰想弄清楚他的田地已经形成了多少水坑。给出约翰田地的示意图，确定当中有多少水坑。

输入格式

Line 1: Two space-separated integers: N and M * Lines 2..N+1: M characters per line representing one row of Farmer John's field. Each character is either 'W' or '.'. The characters do not have spaces between them.

第1行：两个空格隔开的整数：N 和 M 第2行到第N+1行：每行M个字符，每个字符是'W'或'.'，它们表示网格图中的一排。字符之间没有空格。

输出格式

Line 1: The number of ponds in Farmer John's field.

一行：水坑的数量

输入输出样例

输入 #1复制

10 12 W........WW. .WWW.....WWW ....WW...WW. .........WW. .........W.. ..W......W.. .W.W.....WW. W.W.W.....W. .W.W......W. ..W.......W.

输出 #1复制

3

说明/提示

OUTPUT DETAILS: There are three ponds: one in the upper left, one in the lower left, and one along the right side.

思路

这个题目主要就是遍历整个字符数组，然后遇到一个W，总和加一，再调用dfs函数，把与这个W相连的W全部标记为‘.’，不影响接下来的找水坑操作。

代码

#include<stdio.h>

char mp[105][105];

int total;

int n,m;

int next[8][2]={1,0,-1,0,0,1,0,-1,1,1,-1,-1,1,-1,-1,1};//一开始忘记了它有八个方向可以走，一直用四个方向结果一直错

void dfs(int x,int y)

{

/*if(x<0||x>=n||y<0||y>=m||mp[x][y]!='W'){

return;

}*/

mp[x][y]='.';//我们将走过都标记成‘.’

for(int i=0;i<8;i++){//尝试走下一步

int tx=x+next[i][0];

int ty=y+next[i][1];

if(tx>=0&&tx<n&&ty>=0&&ty<m&&mp[tx][ty]=='W'){

/* mp[x][y]='.'; */ dfs(tx,ty);

}

}}

int main()

{

scanf("%d%d",&n,&m);

getchar();

for(int i=0;i<n;i++){

for(int j=0;j<m;j++){

scanf("%c",&mp[i][j]);

}getchar();

}

/*for(int i=0;i<n;i++){

scanf("%s",mp[i]);

}*/

for(int i=0;i<n;i++){

for(int j=0;j<m;j++){

if(mp[i][j]=='W'){//当遇到一个'W'时，水坑总和加一

total++;dfs(i,j);

}

}

}

printf("%d\n",total);

}

然后是抱佛脚

题目背景

kkksc03 的大学生活非常的颓废，平时根本不学习。但是，临近期末考试，他必须要开始抱佛脚，以求不挂科。

题目描述

这次期末考试，kkksc03 需要考 44 科。因此要开始刷习题集，每科都有一个习题集，分别有 s_1,s_2,s_3,s_4s1​,s2​,s3​,s4​ 道题目，完成每道题目需要一些时间，可能不等（A_1,A_2,\ldots,A_{s_1}A1​,A2​,…,As1​​，B_1,B_2,\ldots,B_{s_2}B1​,B2​,…,Bs2​​，C_1,C_2,\ldots,C_{s_3}C1​,C2​,…,Cs3​​，D_1,D_2,\ldots,D_{s_4}D1​,D2​,…,Ds4​​）。

kkksc03 有一个能力，他的左右两个大脑可以同时计算 22 道不同的题目，但是仅限于同一科。因此，kkksc03 必须一科一科的复习。

由于 kkksc03 还急着去处理洛谷的 bug，因此他希望尽快把事情做完，所以他希望知道能够完成复习的最短时间。

输入格式

本题包含 55 行数据：第 11 行，为四个正整数 s_1,s_2,s_3,s_4s1​,s2​,s3​,s4​。

第 22 行，为 A_1,A_2,\ldots,A_{s_1}A1​,A2​,…,As1​​ 共 s_1s1​ 个数，表示第一科习题集每道题目所消耗的时间。

第 33 行，为 B_1,B_2,\ldots,B_{s_2}B1​,B2​,…,Bs2​​ 共 s_2s2​ 个数。

第 44 行，为 C_1,C_2,\ldots,C_{s_3}C1​,C2​,…,Cs3​​ 共 s_3s3​ 个数。

第 55 行，为 D_1,D_2,\ldots,D_{s_4}D1​,D2​,…,Ds4​​ 共 s_4s4​ 个数，意思均同上。

输出格式

输出一行,为复习完毕最短时间。

输入输出样例

输入 #1复制

1 2 1 3 5 4 3 6 2 4 3

输出 #1复制

20

说明/提示

1\leq s_1,s_2,s_3,s_4\leq 201≤s1​,s2​,s3​,s4​≤20。

1\leq A_1,A_2,\ldots,A_{s_1},B_1,B_2,\ldots,B_{s_2},C_1,C_2,\ldots,C_{s_3},D_1,D_2,\ldots,D_{s_4}\leq601≤A1​,A2​,…,As1​​,B1​,B2​,…,Bs2​​,C1​,C2​,…,Cs3​​,D1​,D2​,…,Ds4​​≤60。

#include<stdio.h>

int min=10000000;//使min的初始值为一个大于每个科目最大复习时间的值

int total;//四个科目时间总和

int s[4];//4个科目，每个科目多少题

int time[5][25];//建立一个二维数组存储每个科目每题所花的时间

int left,right,max;//左脑所复习的时间，右脑复习的时间，两者的较大值

void dfs(int x,int y)

{

max=left;//使max为两者的较大值

if(left<right){

max=right;

}

if(y==s[x]){

if(min>max){//当min大于两者最大值，则将max值赋给min

min=max;

return;

}}

else{//搜寻left和right所有可能的值

left=left+time[x][y];

dfs(x,y+1);

left=left-time[x][y];//回溯

right=right+time[x][y];

dfs(x,y+1);

right=right-time[x][y];//回溯

}

}

int main()

{

for(int i=0;i<4;i++){

scanf("%d",&s[i]);

}

for(int i=0;i<4;i++){

for(int j=0;j<s[i];j++){

scanf("%d",&time[i][j]);

}

}

for(int i=0;i<4;i++){

left=right,right=0,min=10000000;

dfs(i,0);

total=total+min;//每个科目最短复习时间总和

}

printf("%d",total);

}

 下午一直在写马的遍历，终于用了一次bfs，因为是求最少步数，所以用bfs会更适合一些，效率也比较高。

题目描述

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

输入格式

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

输出格式

一个 n \times mn×m 的矩阵，代表马到达某个点最少要走几步（左对齐，宽 55 格，不能到达则输出 -1−1）。

输入输出样例

输入 #1复制

3 3 1 1

输出 #1复制

0 3 2 3 -1 1 2 1 4

说明/提示

数据规模与约定

对于全部的测试点，保证 1 \leq x \leq n \leq 4001≤x≤n≤400，1 \leq y \leq m \leq 4001≤y≤m≤400。

这个题跟迷宫求最短路径有些类似，不同的是马是走”日“字形的，所以定义一个next数组为{1,2,2,1,2,-1,1,-2,-1,-2,-2,-1,-2,1,-1,2}即可，一开始因为有两个测试点一直时间超限苦恼很久，改了一下午，发现其实不需要在棋盘的每个点都调用一次bfs，这样时间复杂度很高。

#include<stdio.h>

/*0 3 2

3 -1 1

2 1 4

0 1 2

1 2 2

1 2 1

0 -1 -1

-1 -1 1 */

int mp[405][405];

/*int book[405][405]={0};*/

int n,m,x,y,head,tail;

int next[8][2]={1,2,2,1,2,-1,1,-2,-1,-2,-2,-1,-2,1,-1,2};//八个方向

struct node{

int a;

int b;

int step;//所走的步数

}que[160005];//定义一个结构体队列

void bfs()

{

int flag=0;

int book[405][405]={0};

book[x][y]=1;

while(head<tail){//当队列不为空时

for(int i=0;i<8;i++){//走下一步

int tx=que[head].a+next[i][0];

int ty=que[head].b+next[i][1];

/*if(tx<1||ty<1||tx>n||ty>m||book[tx][ty]==1){

continue;

}

if(book[tx][ty]==0){*/

if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&book[tx][ty]==0){//判断条件

book[tx][ty]=1;//进行走过的标记

que[tail].a=tx;

que[tail].b=ty;

que[tail].step=que[head].step+1;

mp[tx][ty]=que[tail].step;

tail++;

}

/*if(tx==fx&&ty==fy){

flag=1;

break;

}

}}

if(flag==1){

break;

}

head++;

}

/*if(flag==0){

que[tail-1].step=0;

}*/

}head++;}}

int main()

{

scanf("%d%d%d%d",&n,&m,&x,&y);

for(int i=1;i<=n;i++){

for(int j=1;j<=m;j++){

/*if(i==x&&j==y){

continue;}*/

/*int book[405][405]={0};*/

/*for(int p=1;p<=n;p++){

for(int q=1;q<=m;q++){

book[p][q]=0;

}

}*/mp[i][j]=-1;

head=1;//队列初始化

tail=1;

que[tail].a=x;

que[tail].b=y;

que[tail].step=0;

tail++;

}

/*book[x][y]=1;*/

/*mp[i][j]=*/bfs();

}

for(int i=1;i<=n;i++){

for(int j=1;j<=m;j++){

if(i==x&&j==y){

printf("0 ");//起点输出0

}

/*else if(mp[i][j]==0){

printf("-1 ");

}*/

else{

printf("%-5d",mp[i][j]);//记住中间是五个空格

}

}printf("\n");

}

}

然后任务就完成啦，真是不容易呀！ 

 学习时间：8h

明日计划：

明天放假呀

不会真的有人偷偷卷吧？

网址：2022.01.14学习总结 https://www.yuejiaxmz.com/news/view/1328464

相关内容

学习总结、个人学习总结范文、应用文写作学习总结
学习总结
学习方法总结
家务实习总结报告实习学习总结.pptx
大学学习技巧总结
学习方法总结？
学习生活总结
生活学习总结
大一学习生活总结
网络学习总结

随便看看