首页 › 题库 › C/C++编程考级 › C/C++编程七级 › 简答题
简答题 偏难
#7421

红与黑(2023.9) 有一间长方形的房子,地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上,只能向相邻的黑色瓷砖移动。请写一个程序,计算你总…

红与黑(2023.9)

有一间长方形的房子,地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上,只能向相邻的黑色瓷砖移动。请写一个程序,计算你总共能够到达多少块黑色的瓷砖。

时间限制:1000

内存限制:65536

输入

包括多个数据集合。每个数据集合的第一行是两个整数W和H,分别表示x方向和y方向瓷砖的数量。W和H都不超过20。在接下来的H行中,每行包括W个字符。每个字符表示一块瓷砖的颜色,规则如下 1)‘.’:黑色的瓷砖; 2)‘#’:白色的瓷砖; 3)‘@’:黑色的瓷砖,并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。 当在一行中读入的是两个零时,表示输入结束。

输出

对每个数据集合,分别输出一行,显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。

样例输入

6 9 
....#. 
.....# 
...... 
...... 
...... 
...... 
...... 
#@...# 
.#..#. 
0 0

样例输出

45
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//解法1:深搜 #include &lt;bits/stdc++.h&gt; using namespace std; #define N 25 char mp[N][N];//地图 int w, h, ct;//h:行数,w:ct:结果计数 int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};//方向数组 bool vis[N][N]; void dfs(int sx, int sy) { for(int i = 0; i &lt; 4; ++i) { int x = sx + dir[i][0], y = sy + dir[i][1]; if(x &gt;= 1 &amp;&amp; x &lt;= h &amp;&amp; y &gt;= 1 &amp;&amp; y &lt;= w &amp;&amp; vis[x][y] == false &amp;&amp; mp[x][y] != '#') { ct++; vis[x][y] = true; dfs(x, y); } } } int main() { int stx, sty;//起始位置     while(true)     {      cin &gt;&gt; w &gt;&gt; h;      if(w == 0 &amp;&amp; h == 0)      return 0;      for(int i = 1; i &lt;= h; ++i)      for(int j = 1; j &lt;= w; ++j)      {      cin &gt;&gt; mp[i][j];      if(mp[i][j] == '@')      stx = i, sty = j;      }      memset(vis, 0, sizeof(vis));//多组数据,注意状态还原      ct = 1;      vis[stx][sty] = true; dfs(stx, sty);      cout &lt;&lt; ct &lt;&lt; endl; }     return 0; }</pre><pre class="brush:cpp;toolbar:false">//解法2:广搜 #include &lt;bits/stdc++.h&gt; using namespace std; #define N 25 struct Node { int x, y; Node(){} Node(int a, int b):x(a),y(b){} }; char mp[N][N];//地图 int w, h;//w:列数 h:行数 int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};//方向数组 bool vis[N][N]; int bfs(int sx, int sy)//传入起始位置 { queue&lt;Node&gt; que; vis[sx][sy] = true; que.push(Node(sx, sy)); int ct = 1;//计数,看可以到达几个黑色格子 while(que.empty() == false) { Node u = que.front(); que.pop(); for(int i = 0; i &lt; 4; ++i) { int x = u.x + dir[i][0], y = u.y + dir[i][1]; if(x &gt;= 1 &amp;&amp; x &lt;= h &amp;&amp; y &gt;= 1 &amp;&amp; y &lt;= w &amp;&amp; vis[x][y] == false &amp;&amp; mp[x][y] != '#') { vis[x][y] = true; que.push(Node(x, y)); ct++; } } } return ct; } int main() { int stx, sty;     while(true)     {      cin &gt;&gt; w &gt;&gt; h;      if(w == 0 &amp;&amp; h == 0)      return 0;      for(int i = 1; i &lt;= h; ++i)      for(int j = 1; j &lt;= w; ++j)      {      cin &gt;&gt; mp[i][j];      if(mp[i][j] == '@')      stx = i, sty = j;      }      memset(vis, 0, sizeof(vis));      cout &lt;&lt; bfs(stx, sty) &lt;&lt; endl; }     return 0; }</pre><pre class="brush:cpp;toolbar:false">//解法3: #include&lt;iostream&gt; #include&lt;cstdio&gt; #include&lt;cstdlib&gt; #include&lt;cstring&gt; #define N 1001 using namespace std; int m,n; char ch; int maps[N][N]; int vis[N][N]; int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}}; int cnt; void dfs(int x,int y) {     for(int i=0;i&lt;4;i++)     {         int nx=x+dir[i][0];         int ny=y+dir[i][1];         if(nx&gt;=1&amp;&amp;ny&gt;=1&amp;&amp;nx&lt;=n&amp;&amp;ny&lt;=m&amp;&amp;vis[nx][ny]==0&amp;&amp;maps[nx][ny]==1)         {             vis[nx][ny]=1;             cnt++;             dfs(nx,ny);         }     } } int main() {     while(scanf("%d%d",&amp;m,&amp;n)!=EOF&amp;&amp;m&amp;&amp;n)     {         int x,y;         cnt=1;         memset(vis,0,sizeof(vis));         memset(maps,0,sizeof(maps));           for(int i=1;i&lt;=n;i++)             for(int j=1;j&lt;=m;j++)             {                 cin&gt;&gt;ch;                 if(ch=='@')                 {                     x=i;                     y=j;                     maps[i][j]=1;                 }                 if(ch=='.')                     maps[i][j]=1;                 if(ch=='#')                     maps[i][j]=0;             }         vis[x][y]=1;         dfs(x,y);         cout&lt;&lt;cnt&lt;&lt;endl;     }     return 0; }</pre><p><br/></p>
这道题暂未补解析。