bfs

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N=22;
char g[N][N];
int st[N][N];

int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};



typedef pair<int,int> pii;

int main()
{
    int m,n;
    while(cin>>m>>n,n||m)
    {
        int sx,sy;
        int res=0;
        memset(st,0,sizeof st);
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                cin>>g[i][j];
                if(g[i][j]=='@')
                {
                    sx=i,sy=j;
                }
            }
        }
        //cout<<sx<<sy<<endl;

        queue<pii> q;
        q.push({sx,sy});
        st[sx][sy]=1;
        res++;
        while(q.size())
        {
            auto t=q.front();
            q.pop();

            for(int i=0;i<4;i++)
            {
                int a=t.first+dx[i];
                int b=t.second+dy[i];
                if(st[a][b]==0&&a>=1&&a<=n&&b>=1&&b<=m&&g[a][b]=='.')
                {

                    q.push({a,b});
                    res++;
                    st[a][b]=1;
                }
            }


        }
        cout<<res<<endl;

    }
    return 0;
}

dfs函数为判断与这个点连通的点的数量

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N=22;
int m,n;
char g[N][N];
int st[N][N];

int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};

int dfs(int x,int y)
{

    int cnt=1;
    st[x][y]=1;
    for(int i=0;i<4;i++)
    {
        int a=x+dx[i];
        int b=y+dy[i];
        if(a>=1&&a<=n&&b>=1&&b<=m&&st[a][b]==0&&g[a][b]=='.')
        {
            cnt += dfs(a,b);
        }

    }
    return cnt;
}
int main()
{

    while(cin>>m>>n,n||m)
    {
        int sx,sy;
        int res=0;
        memset(st,0,sizeof st);
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                cin>>g[i][j];
                if(g[i][j]=='@')
                {
                    sx=i,sy=j;
                }
            }
        }


        cout<<dfs(sx,sy)<<endl;

    }
    return 0;
}

二刷。dfs内部搜索，不需要回复现场

#include <iostream>
#include <cstring>

using namespace std;

const int N=22;
int n,m;
char g[N][N];
int st[N][N];
int sx,sy;
int dx[]={0,1,-1,0};
int dy[]={1,0,0,-1};

int dfs(int x,int y)
{
    int cnt=1;
    st[x][y]=1;
    for(int i=0;i<4;i++)
    {
        int a=x+dx[i];
        int b=y+dy[i];
        if(a>n||a<1||b>m||b<1||(st[a][b]==1)||g[a][b]=='#') continue;
        cnt+=dfs(a,b);

    }
    return cnt;
}

int main()
{
    while(cin>>m>>n,m||n)
    {
        memset(st,0,sizeof st);
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                cin>>g[i][j];
                if(g[i][j]=='@')
                {
                    sx=i;
                    sy=j;
                }
            }
        }
        cout<<dfs(sx,sy)<<endl;
    }

    return 0;
}

三刷，还是不会记录总方案数

用一个全局变量res代替。但实际可以这么写

int dfs(int x,int y)
{
    int cnt=1;
    for(int i=0;i<4;i++)
    {
        ...
        cnt+=dfs(a,b);

    }
    return cnt;
}

#include <iostream>
#include <cstring>

using namespace std;

const int N=30;
int n,m;
char g[N][N];
int st[N][N];
int sx,sy;
int dx[]={0,1,-1,0};
int dy[]={1,0,0,-1};
int res;

void dfs(int x,int y)
{
    st[x][y]=1;
    for(int i=0;i<4;i++)
    {
        int a=x+dx[i];
        int b=y+dy[i];
        if(a>=1&& a<=n && b>=1 &&b<=m &&st[a][b]==0 && g[a][b]=='.')
        {
            res++;
            dfs(a,b);
        }
    }
    return;
}

int main()
{
    while(cin>>m>>n,n|m)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                cin>>g[i][j];
                if(g[i][j]=='@') 
                {
                    sx=i;
                    sy=j;
                }
            }
        }
        memset(st,0,sizeof st);
        res=0;
        dfs(sx,sy);
        cout<<res+1<<endl;

    }

    return 0;
}

2023/12/1

在复习了上一题之后，快速ac
dfs，没什么难度

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N=22;
char g[N][N];
int st[N][N];

int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};

int res;
int n,m;

int dfs(int x,int y)
{
    // 走到了一块地板，总数++
    res ++;
    st[x][y] = 1;
    for(int i=0;i<4;i++)
    {
        int a=x+dx[i];
        int b=y+dy[i];

        if(a<1 || a>n || b<1 || b>m) continue;
        if(st[a][b]) continue;
        if(g[a][b] == '#') continue;

        dfs(a,b);
    }
}

int main()
{
    while(cin>>m>>n, n||m)
    {
        int sx,sy;
        res = 0;
        memset(st, 0, sizeof(st));
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                cin>>g[i][j];
                if(g[i][j] == '@')
                {
                    sx = i;
                    sy = j;
                }
            }
        }

        dfs(sx, sy);
        cout<<res<<endl;

    }

    return 0;
}