【蓝桥杯练习--DFS】1113. 红与黑

1113. 红与黑

#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int N=25;int n,m;
char g[N][N];
bool st[N][N];
int dx[4]={
    -1,0,1,0},dy[4]={
    0,1,0,-1};int dfs(int x,int y)
{
    int cnt=1;st[x][y]=true;for(int i=0;i<4;i++){
    int a=x+dx[i], b=y+dy[i];if(a<0 || a>=n || b<0 || b>=m) continue;if(g[a][b]!='.') continue;if(st[a][b]) continue;cnt+=dfs(a,b);}return cnt;
}int main()
{
    while(cin>>m>>n, n||m){
    for(int i=0;i<n;i++) cin>>g[i];int x,y;for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(g[i][j]=='@')x=i,y=j;memset(st, 0, sizeof st);cout << dfs(x,y) << endl;}return 0;
}

收获：

1. 报错如下

error: array bound is not an integer constant before ‘]’ token

声明数组时，数组大小必须使用const变量表示

另：
如何使用BFS求解呢？【下面代码有问题，但还没有理解是哪里出的问题】

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;struct Point
{
    int x,y;  
};const int N=21;int W,H;
Point start;
char g[N][N];   //存放迷宫地图
int dist[N][N]; //每个点的状态已经从起点到此处的距离
Point q[N*N];   //遍历的顺序（树状结构的每层）int dx[4]={
    0,0,-1,1}, dy[4]={
    -1,1,0,0};int bfs(Point start)
{
    int s=0,e=0;q[0]=start;memset(dist,-1,sizeof dist);dist[start.x][start.y]=0;while(s<=e){
    Point t=q[s++];     //后++：先运算 再加1for(int i=0;i<4;i++){
    int x=t.x+dx[i], y=t.y+dy[i];if(x<0 || x>=W || y<0 || y>=H) continue;    //出界if(dist[x][y]!=-1) continue;    //已经遍历if(g[x][y]=='#') continue;dist[x][y]=dist[t.x][t.y]+1;if(e>W*H) return dist[q[e].x][q[e].y];// cout << q[e].x << " " << q[e].y << " " << dist[q[e].x][q[e].y] << endl;q[++e]={
    x,y};}}return dist[q[e].x][q[e].y];
}int main()
{
    while(scanf("%d%d",&W,&H), W || H){
    for(int i=0;i<W;i++){
    scanf("%s",g[i]);  //直接读取一行for(int j=0;j<H;j++)if(g[i][j]=='@') start={
    i,j};}int distance=bfs(start);printf("%d\n",distance);}return 0;
}