2022.1.14

目录

P1101 单词方阵

题目描述

输入格式

输出格式

输入输出样例

思路

出错点

代码实现 

P1596 [USACO10OCT]Lake Counting S

题目描述

输入格式

输出格式

输入输出样例

说明/提示

        思路

代码实现 

P1162 填涂颜色

题目描述

输入格式

输出格式

输入输出样例

说明/提示

        思路

         代码实现


        

P1101 单词方阵

题目描述

给一n \times nn×n的字母方阵,内可能蕴含多个“yizhong”单词。单词在方阵中是沿着同一方向连续摆放的。摆放可沿着 88 个方向的任一方向,同一单词摆放时不再改变方向,单词与单词之间可以交叉,因此有可能共用字母。输出时,将不是单词的字母用*代替,以突出显示单词。例如:

输入:
    8                     输出:
    qyizhong              *yizhong
    gydthkjy              gy******
    nwidghji              n*i*****
    orbzsfgz              o**z****
    hhgrhwth              h***h***
    zzzzzozo              z****o**
    iwdfrgng              i*****n*
    yyyygggg              y******g

输入格式

第一行输入一个数nn。(7 \le n \le 1007≤n≤100)。

第二行开始输入n \times nn×n的字母矩阵。

输出格式

突出显示单词的n \times nn×n矩阵。

输入输出样例

输入 #1复制

7
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa

输出 #1复制

*******
*******
*******
*******
*******
*******
*******

输入 #2复制

8
qyizhong
gydthkjy
nwidghji
orbzsfgz
hhgrhwth
zzzzzozo
iwdfrgng
yyyygggg

输出 #2复制

*yizhong
gy******
n*i*****
o**z****
h***h***
z****o**
i*****n*
y******g

思路

1、定义一个二维数组存储八个方向:

                int dir[][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};

2、首先在矩阵中从八个方向搜索,找到y和i相连的方向k,以k方向进行DFS

3、当搜索到第7个单词‘g’时,用vis标记此路径

4、最后遍历二维数组,将标记的字符输出,未标记的输出*

出错点

 1、单词矩阵的输入

        错误版:

        for(int i=0;i<n;i++)//n*n单词矩阵
    {
        for(int j=0;j<n;j++)
        {
            scanf("%c",&ch[i][j]);
        }
           getchar();
    } 

        正确版:

for(int i=0;i<n;i++)//n*n单词矩阵 
        scanf("%s",ch[i]);

 2、临界点

if(ch[xx][yy]==a[cnt+1]||cnt==6)//这里的6第一次写成了7,(因为cnt是从0开始的)

代码实现 

#include<stdio.h>
struct node
{
    int x,y;
}c[1010];//记录路径
char ch[1010][1010],a[]="yizhong";//ch保存单词矩阵,a保存“yizhong”便于匹配
int vis[1010][1010];
int dir[][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};//八向的常量数组
void dfs(int x,int y,node c[],int k,int cnt)
{
    if(cnt==7){
        for(int i=0;i<7;i++)
            vis[c[i].x][c[i].y]=1;
    }
    else{
        int dx=x+dir[k][0];//沿着正确的k方向搜索
        int dy=y+dir[k][1];
        if(cnt==6||ch[dx][dy]==a[cnt+1]){
            c[cnt].x=x;c[cnt].y=y;
            dfs(dx,dy,c,k,cnt+1);
        }
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)//n*n单词矩阵 
        scanf("%s",ch[i]);
    for(int i=0;i<n;i++)//搜索y,i相连的可能的方向k,以k为方向进行DFS
        for(int j=0;j<n;j++)
            if(ch[i][j]=='y') for(int k=0;k<8;k++){
                    int x=i+dir[k][0];
                    int y=j+dir[k][1];
                    if(ch[x][y]=='i')
                        dfs(i,j,c,k,0);
                    }
    for(int i=0;i<n;i++){//输出结果
        for(int j=0;j<n;j++)
            if(vis[i][j]) printf("%c",ch[i][j]);
            else printf("*");
        printf("\n");
    }
    return 0;
}

P1596 [USACO10OCT]Lake Counting S

题目描述

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.

思路

1、典型的连通块问题

2、定义八个方向的二维数组:int dir[][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};

3、遍历这个矩阵,当遍历到w时,我们可以从这个坐标开始在八个方向搜索,将搜索到的w换为 .

4、用cnt计数,当有一组w时,cnt++

5、输出cnt

代码实现 

#include<stdio.h>
int n,m,cnt=0;
char a[1000][1000];//矩阵
int dir[][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
void dfs(int x,int y)
{
	a[x][y]='.';
	for(int i=0;i<8;i++)//将坐标x,y8个方向全搜一遍
	{
		int xx=x+dir[i][0];
		int yy=y+dir[i][1];
		if(a[xx][yy]=='W')
			dfs(xx,yy);
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++)
		scanf("%s",a[i]);
	for(int i=0;i<n;i++)
	for(int j=0;j<m;j++)
	{
		if(a[i][j]=='W')
		{
			cnt++;
			dfs(i,j);
		}
	}
	printf("%d",cnt);
	return 0;
} 

P1162 填涂颜色

题目描述

由数字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


思路

1、数组a[][]存图,数组b[][]标记

2、a[][]输入从1~n

3、从a[0][0]开始深搜,把搜的0用b[][]标记为1

4、把标记的全都变成1

5、从1~n便利二维数组a把0全都变成2

6、再把标记的全都变回0

气死我了不小心把y写成了x,运行结果一直不对,检查了将近1个小时

上一篇:重邮2020复试题


下一篇:[LeetCode] 1282. Group the People Given the Group Size They Belong To 用户分组