代码(BFS)
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
void BFS(int x, int y);
int step;
int n, m;
int start_x, start_y;
char mp[30][30];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0}; // 右、下、左、上,4个方向的 搜索
struct node
{
int x, y;
};
int main()
{
while(cin>>n>>m && (n||m))
{
step = 0;
for (int i=0; i<m; i++)
{
for (int j=0; j<n; j++)
{
cin>>mp[i][j];
if (mp[i][j] == '@')
{
start_x = i;
start_y = j;
}
}
}
BFS(start_x, start_y);
}
return 0;
}
void BFS(int x, int y)
{
queue <node> q;
node start, next; // 当前的点的坐标、下一步的点的坐标
start.x = x;
start.y = y;
q.push(start);
mp[start.x][start.y] = '#'; // 压入队列的同时,标记此点已经走过,不可以继续走
while (!q.empty())
{
start.x = q.front().x;
start.y = q.front().y;
q.pop();
step++; // 出队的同时,步数 +1
for (int i=0; i<4; i++)
{
next.x = start.x + dx[i];
next.y = start.y + dy[i];
if(next.x >= 0 && next.x < m && next.y >= 0 && next.y < n && mp[next.x][next.y] == '.')
{
q.push(next);
mp[next.x][next.y] = '#';
}
}
}
cout<<step<<endl;
}
代码(DFS)
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
void DFS(int x, int y);
int step;
int n, m;
char mp[30][30];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0}; // 右、下、左、上,4个方向的 搜索
int main()
{
int start_x, start_y;
while(cin>>n>>m && (m||n))
{
step = 0;
for (int i=0; i<m; i++) // 输入地图
{
for (int j=0; j<n; j++)
{
cin>>mp[i][j];
if (mp[i][j] == '@') // 寻找起点
{
mp[i][j]='#';
start_x = i;
start_y = j;
}
}
}
DFS(start_x, start_y); // 开始搜索
cout<<step<<endl;
}
return 0;
}
void DFS(int x, int y)
{
mp[x][y] = '#'; // 标记当前 x y 已经走过
step++; // 步数 +1
for (int i=0; i<4; i++) // 4个方向的 搜索
{
int next_x = x + dx[i];
int next_y = y + dy[i];
if (next_x >= 0 && next_x < m && next_y >= 0 && next_y < n && mp[next_x][next_y] == '.') // 判断当前位置的下一步
{
DFS(next_x, next_y); // 下一步 未越界,且可以走时,进入下一层函数中搜索
}
}
}