目录
P1596 [USACO10OCT]Lake Counting S
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个小时