红与黑
红与黑
描述:
有一间长方形的房子,地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上,只能向相邻的黑色瓷砖移动。请写一个程序,计算你总共能够到达多少块黑色的瓷砖。
输入:
包括多个数据集合。每个数据集合的第一行是两个整数W和H,分别表示x方向和y方向瓷砖的数量。W和H都不超过20。在接下来的H行中,每行包括W个字符。每个字符表示一块瓷砖的颜色,规则如下
1)‘.’:黑色的瓷砖;
2)‘#’:白色的瓷砖;
3)‘@’:黑色的瓷砖,并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。
当在一行中读入的是两个零时,表示输入结束。
输出:
对每个数据集合,分别输出一行,显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。
样例输入
6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
样例输出
45
#include#include { cin>>map[i]; for(int j=0;j#include using namespace std; int m,n;//m代表的是行,n代表的列 int beginx,beginy;//其实黑色瓷砖的点 int x[4]={0,0,1,-1},y[4]={1,-1,0,0};//右,左,下,上 int total; bool mark[20][20]; char map[20][20];//map 记录的是该表 bool check(int x,int y) { if(x =0&&y>=0)return 1;//判断是否越界 return 0; } void dfs(int r,int c) { for(int i=0;i<4;i++) //往下一层走的条件是(1)该点没有越界 (2)该点没有走过 (3)该点是黑色的瓷砖 if(check(r+x[i],c+y[i])&&!mark[r+x[i]][c+y[i]]&&map[r+x[i]][c+y[i]]=='.') { r+=x[i]; c+=y[i]; total++;//发现一个点+1个 mark[r][c]=1;//该点走过了 dfs(r,c); r-=x[i]; c-=y[i]; } } int main() { //当m n 都为0的时候,表示没有数据了 while(cin>>n>>m,n>0){ // while(scanf("%d%d",&n,&m)&&m&&n) // { memset(mark,0,sizeof(mark));//置标记,刚开始所有的点没有走过 total=0; for(int i=0;i ) ) if(map[i][j]=='@'){beginx=i;beginy=j;} } dfs(beginx,beginy); cout< 1<<endl; } }
BFS解决该问题:
#include#include 判断坐标是否越界 return true; else return false; } int bfs(int x,int y) { ans=0; queue#include #include using namespace std; int beginx,beginy,ans,m,n; char map[22][22];//地图 bool vis[22][22];//表示访问过没有 int move[4][2] = {0,1,0,-1,1,0,-1,0};//移动 其中a[i][0]表示X移动, a[i][1]表示y移动. struct AC { int x,y; }node,temp; bool judge (int x,int y) { if (x>=0 && x =0 && y // q; node.x = x; node.y = y; q.push(node); while (!q.empty())//模板写法 { AC top = q.front(); q.pop(); for (int i=0;i<4;i++) { temp.x = top.x + move[i][0];//分别上下左右走动 temp.y = top.y + move[i][1]; if (judge(temp.x,temp.y) && !vis[temp.x][temp.y] && map[temp.x][temp.y]=='.') { ans++; //能走的话就加一下 q.push(temp); vis[temp.x][temp.y] = true; } } } return ans; } int main() { //当m n 都为0的时候,表示没有数据了 while(cin>>n>>m,n>0){ memset(vis,0,sizeof(vis));//置标记,刚开始所有的点没有走过 ans=0; for(int i=0;i ) { cin>>map[i]; for(int j=0;j ) if(map[i][j]=='@'){beginx=i;beginy=j;} } bfs(beginx,beginy); cout< 1<<endl; } }
#include
#include
#include
using namespace std;
char room[21][21];
int beginx,beginy,Wx,Wy;
int num=1;
struct node{
int x,y;
};
bool check(int x,int y){
if(x=0&&y=0) return true;
else
return false;
}
int dir[4][2]={
{-1,0},
{0,-1},
{1,0},
{0,1}
};
void BFS(int x,int y ){
queueq;
node start,next;
start.x=x;
start.y=y;
q.push(start);
while (!q.empty())
{
start= q.front();
q.pop();
for (int i = 0; i < 4; i++)
{
next.x = start.x+dir[i][0];
next.y = start.y+dir[i][1];
if(check(next.x,next.y)&&room[next.x][next.y]=='.'){
q.push(next);
num++;
room[next.x][next.y]='#';
}
}
}
}
总结:
1)对于遍历方格的形式,很喜欢开一个x 数组和一个y数组,走四个方向;一般两种形式,采用一维数组或者二维数组
2)对于memset()的应用:
库------> #include声明
void *memset(void *str, int c, size_t n)
参数
- str -- 指向要填充的内存块。
- c -- 要被设置的值。该值以 int 形式传递,但是函数在填充内存块时是使用该值的无符号字符形式。
- n -- 要被设置为该值的字节数。
#include #include
int main ()
{
char str[50];
strcpy(str,"This is string.h library function");
puts(str);
memset(str,'$',7);
puts(str);
return(0);
}
结果:
This is string.h library function $$$$$$$ string.h library function
3)对于cin及scanf的使用,有了进一步了解