学步园

题意：

一个有障碍物的地图，给定起点，问有多少个地图中的方块是可以走到的？

类似于地图问题，由于只要求能达到的方块数，不涉及第几步走到哪里这些信息。

所以可以使用队列帮助的BFS，走到的地方标记之，计数器++，当队列为空时，搜索结束，计数器即为结果。

使用了迷宫问题的几个典型处理手段：

1）外围加一圈围墙，将边界一般化；

2）使用一个位移数组，帮助搜索。

代码如下：

//POJ 1979<br /> #include <queue><br /> #include <iostream></p> <p>using namespace std;</p> <p>struct position<br /> {<br /> int x;<br /> int y;<br /> };</p> <p>int main()<br /> {<br /> int W,H;<br /> while (true)<br /> {<br /> cin>>W>>H;<br /> if(W==0&&H==0)<br /> break;<br /> int grids[22][22] = {0};</p> <p> //围墙，消除边界差异性<br /> for (int i = 0;i <= W+1;i++)<br /> {<br /> grids[0][i] = 1; //顶<br /> grids[H+1][i] = 1; //底<br /> }<br /> for (int i = 0;i <= H+1;i++)<br /> {<br /> grids[i][0] = 1; //左边<br /> grids[i][W+1] = 1; //右边<br /> }</p> <p> //位移数组<br /> position offset[4];<br /> offset[0].x = 1;<br /> offset[0].y = 0;<br /> offset[1].x = 0;<br /> offset[1].y = 1;<br /> offset[2].x = -1;<br /> offset[2].y = 0;<br /> offset[3].x = 0;<br /> offset[3].y = -1;</p> <p> char ch;<br /> position start;<br /> for (int i = 1; i <= H;i++)<br /> {<br /> for (int j = 1; j<= W;j++)<br /> {<br /> cin>>ch;<br /> if (ch == '.')<br /> {<br /> grids[i][j] = 0;<br /> }<br /> else if (ch == '#')<br /> {<br /> grids[i][j] = 1;<br /> }<br /> else if (ch == '@')<br /> {<br /> start.x = j;<br /> start.y = i;<br /> grids[i][j] = 1;<br /> }<br /> }<br /> }<br /> queue<position> q;<br /> int count = 1;<br /> q.push(start);<br /> position here,next;<br /> while (!q.empty())<br /> {<br /> here = q.front();<br /> q.pop();<br /> for (int i = 0;i <= 3;i++)<br /> {<br /> next.x = here.x + offset[i].x;<br /> next.y = here.y + offset[i].y;<br /> if (grids[next.y][next.x] == 0)<br /> {<br /> q.push(next);<br /> grids[next.y][next.x] = 1;<br /> count++;<br /> }<br /> }<br /> }<br /> cout<<count<<endl;<br /> }<br /> }