Acwing 1113.红与黑
题目链接:
思路:宽搜
本题宽搜的要点:
- 起点:输入数据时判断
@
的坐标,就是起点 - 终点:没有终点,直到无路可走,即结束
- 搜索的方式:上下左右四个方向,如果是符号
.
即可行走
宽搜的步骤:
- 将起点坐标插入队列,并标记
- 获取队头坐标,并弹出
- 以该点进行搜索,符合条件的坐标插入队列,并标记
- 循环,直到终点
代码:
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
typedef pair<int,int> site;
const int N = 25;
char q[N][N];
int main()
{
int n,m;
cin>>n>>m;
while( n != 0 && m != 0)
{
int res = 0;
queue<site> que;
// 上右下左
int dx[] = {-1,0,1,0},dy[] = {0,1,0,-1};
for(int i = 0; i < m; i++ )
for(int j = 0; j < n; j ++)
{
char tmp;
cin>>tmp;
q[i][j] = tmp;
//第一步:将起点坐标插入队列,并标记
if(tmp == '@'){
que.push({i,j});
q[i][j] = '#';
}
}
//第四步:直到队列为空,表示没有任何的坐标可以通过,即表示结束
while(!que.empty())
{
//第二步:获取队头,弹出
site s = que.front();
que.pop();
res ++;
//第三步:搜索方式:以该点进行搜索,符合条件插入队列,并标记
for(int i = 0; i < 4; i ++)
{
int a = s.first,b = s.second;
a += dx[i],b += dy[i];
if(q[a][b] == '.')
{
que.push({a,b});
q[a][b] = '#';
}
}
}
cout << res << endl;
cin>>n>>m;
}
return 0;
}