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

明日计划:

明天放假呀

不会真的有人偷偷卷吧?

 

上一篇:Android向系统日历中添加日程事件


下一篇:Struts2 之 Action 类访问 WEB 资源