填涂颜色
解题思路：依次从遍历围圈的外围，如果有数==0，那么就将该数赋值为5，利用深搜将和外围相连的为0 的数全部赋值为5，然后再将剩下为0的数赋值为2，再把之前赋值为5的数重新赋值为0，输出涂色后的图形。
题目描述
由数字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≤n≤30)
接下来nn行，由00和11组成的n×n的方阵。
方阵内只有一个闭合圈，圈内至少有一个0。
//感谢黄小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≤n≤30
#include<iostream>
using namespace std;
char a[35][35];
int n;
int dfs(int sx,int sy)
{
int nx,ny;
int next[4][2]= {{0,1},{0,-1},{1,0},{-1,0}};//能够移动的方向
int i;
for(i=0; i<4; i++)
{
nx=sx+next[i][0];
ny=sy+next[i][1];
if(nx>=0&&ny>=0&&nx<n&&ny<n)
{
if(a[nx][ny]==0)
{
a[nx][ny]=5;//将外围开始的连着的0 全部赋值为5
dfs(nx,ny);
}
}
}
}
int main()
{
int l,j;
scanf("%d",&n);
for(l=0; l<n; l++)
for(j=0; j<n; j++)
{
scanf("%d",&a[l][j]);
}//输入地图
for(l=0; l<n; l++)
{
if(a[l][0]==0)
{
a[l][0]=5;
dfs(l,0);
}//遍历第一列的数
if(a[l][n-1]==0)
{
a[l][n-1]=5;
dfs(l,n-1);
}遍历最后一列的数
}
for(j=0; j<n; j++)
{
if(a[0][j]==0)
{
a[0][j]=5;
dfs(0,j);
}//遍历第一行的数
if(a[n-1][j]==0)
{
a[n-1][j]=5;
dfs(n-1,j);
}//遍历最后一行的数
}
for(l=0; l<n; l++)
{
for(j=0; j<n; j++)
{
if(a[l][j]==0)
a[l][j]=2;
}
}
for(l=0; l<n; l++)
{
for(j=0; j<n; j++)
{
if(a[l][j]==5)
a[l][j]=0;
}
}
for(l=0; l<n; l++)
{
for(j=0; j<n; j++)
{
printf("%d ",a[l][j]);
}
printf("\n");
}
}
水坑问题
由于近期的降雨，雨水汇集在农民约翰的田地不同的地方。我们用一个NxM(1<=N<=100;1<=M<=100)网格图表示。每个网格中有水('W') 或是旱地('.')。一个网格与其周围的八个网格相连，而一组相连的网格视为一个水坑。约翰想弄清楚他的田地已经形成了多少水坑。给出约翰田地的示意图，确定当中有多少水坑。
第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
#include<iostream>
using namespace std;
char a[105][105];
int n,m;
int dfs(int sx,int sy)
{
int nx,ny;
int next[8][2]= {{0,1},{0,-1},{1,0},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};
int i;
for(i=0; i<8; i++)
{
nx=sx+next[i][0];
ny=sy+next[i][1];
if(nx>=0&&ny>=0&&nx<n&&ny<m)
{
if(a[nx][ny]=='W')
{
a[nx][ny]='.';
dfs(nx,ny);
}
}
}
}
int main()
{
int l,j,k=0;
scanf("%d%d",&n,&m);
for(l=0; l<n; l++)
{
scanf("%s",a[l]);//在用%c输入字符数组时结尾会有'\0'结束
}
for(l=0; l<n; l++)
{
for(j=0; j<m; j++)
{
if(a[l][j]=='W')
{
k++;//每找到一个新的W就数量k加1
a[l][j]='.';//将走过的路标记为.
dfs(l,j);
}
}
}
printf("%d",k);
}
今天写了几个dfs的题，写了一下循环链表的代码，看了几页大话数据结构
明日计划
继续学习双向链表和bfs
