dfs是不是自己保证不会走重复的块，因此不用boolean数组来判断某一个块是否走过了

不是，走过了就会变为‘#’，判断了’#’就会跳过dfs的，不会继续向下，也就不重复了，‘#’相当于boolean了

ヽ(￣▽￣)و

也可以用bool数组 只是博主的处理方式让他可以不用bool数组

自己第一次写出了一个bfs，各位可以去看上一道题写这个,真的很好想的bb
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]

using namespace std;

#define x first
#define y second
//参考y总的献给阿尔吉侬的花束
typedef pair[HTML_REMOVED] PII;
const int N=25;
char g[N][N];
bool st[N][N];
int res;
int n,m;

int bfs(PII start)
{
queue[HTML_REMOVED] q;
memset(st,false,sizeof st);
int dx[4]={-1,0,0,1};
int dy[4]={0,1,-1,0};
//十分重要的初始化
//一开始就被搜索过了
st[start.x][start.y]=true;
q.push(start);

while(q.size())
{
    PII t=q.front();
    q.pop();

    for(int i=0;i<4;i++)
    {
        int x=t.x+dx[i],y=t.y+dy[i];
        if(x>=0&&x<n&&y>=0&&y<m&&g[x][y]=='.'&&!st[x][y])
        {
            res++;
            st[x][y]=true;
            q.push({x,y});
        }
    }
}

}

int main()
{
//注意这个题的行和列输入相反
//读入 0 就会停止了
while (cin >> m >> n, n || m)
{
for (int i = 0; i < n; i ) cin >> g[i];
PII start;
for (int i = 0; i < n; i )
for (int j = 0; j < m; j ++ )
if (g[i][j] == ‘@’)
{
start={i,j};
}
bfs(start);
cout<<res+1<< endl;
res=0;
}
return 0;
}

同样dfs也是一样的,因为和bfs一样都使用了for(循环i)
然后比如第一条线路全贯通cnt就得出答案了,其他的都是平行的另几个cnt；
个人理解(求大佬指正)

比较常见的dfs是不同的方案相互不干扰，各走各的，最终取最优，但这道题不太一样
第一：它是破坏现场的，不同方案不仅会干扰，且共用一个状态
第二：只要前人走过就会变为’#’，所以cnt其实是反映了所有的路线共同努力的结果，cnt不是平行的，是共有

//我想说一下这个题bfs的cnt,我一开始对这个cnt会不会加重有疑惑
//然后最后我发现比如一开始往两个方向走,cnt都从1的状态变化
//而且那么比如第二部另一个走到了尽头那么cnt=2结束了,而另一个也是cnt
=2,可是会仅需往前走,继续++

大佬，那可不可以开个数组dist[][]记录呢

不会加重的，bfs每次加入队列时都会保证是没有走过的点（不然就会通过判断st跳过了，同理跳过了也不会让cnt增加），所以最后bfs反映的所以可走且不重复的点，直到所有能走的点都走过（这里再提一点，你理解bfs虽然往小了看是一条条路，但其实bfs反倒是更像是从某个点开始传染，染过的不会再染了）

🎉🎉🎉

请教一下大家，我定义二维数组时，用int类型而不是char类型，为什么不能通过。即int g[N][N]，而不是char g[N][N]。（cin>>’@’或‘#’或‘.’，不一样转化成ASCII吗）

嘶，为什么字符串不用字符数组存呢？读是读进去了，但处理的时候，比如你输出一个g[i][j]的时候会当作数字处理的，而不是字符串，读没问题，输出和判断是有问题的

如果int g[N][N]，g[1][1]=’#’; if (g[1][1]==’#’) cout<<”Yes”; 我试了以上代码，是可以输出Yes。判断是没有问题的，都转化成对应的整数。该程序中不需要输出（理论上也能输出对应的数字）。所以，感觉是可以定义成int的二维数组，不知道为什么不能通过

我试的就不行

####贴个代码

#include<iostream>
#include<cstring>

using namespace std;

const int N=30;

int g[N][N];
int n,m,cnt;
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

void dfs(int x,int y)
{
    g[x][y]='#';
    cnt++;
    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 || g[a][b]=='#') continue;
        dfs(a,b);
    }
}


int main()
{
    while(cin>>m>>n,n||m)
    {
        cnt=0;
        for(int i=0;i<n;i++) scanf("%s",g[i]);
        int x,y,flag=0;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++) {
                cout<< g[i][j];
                if(g[i][j] == '@') cout<< "YEs" <<endl;
            }
            //     if(g[i][j]=='@')
            //     {
            //         x=i,y=j;
            //         flag=1;
            //     }
            // if(flag) break;
            cout<<endl;
        }
        dfs(x,y);
        cout<< cnt <<endl;
    }
    return 0;
}

是的，在红与黑的程序里，通过不了。但是以下程序可以输出“yes”，这就是我不理解的地方，为什么在红与黑的程序中不可行：见代码：
#include [HTML_REMOVED]

using namespace std;
int main()
{
int a[50][50];
a[1][1]=’@’;
if(a[1][1]==’@’) cout<<”yes”;
return 0;
}

你读进来和你直接赋值是不一样的，就像你说的，读是时候都是ASCII，但如果是int就会存为数字，如果是char虽然也是数字，但是底层char是一字节，int是四字节同时还有符号位，内部处理也是不一样的，符号还是存char就好

####贴个代码

#include<iostream>
#include<cstring>

using namespace std;
int main()
{
    int a[50][50];
    scanf("%s", a[0]);
    cout<< a[0][0] <<endl;
    char c = '#';
    if(a[2][2] == c) cout<< "yes";
    return 0;
}

tql

请问为什么dfs中把g[x][y]='#',cnt++;放在dfs(a,b)；前面答案就不正确了呢？（在进入下一次dfs之前就修改成#并cnt++）。考虑了起点的黑块。

我懂了，还是没考虑起点的黑块。如果按照上面的方法，起点的黑块没有修改成红块，结果就错了。如果要按上面这种方法，需要在进入dfs之前就修改成红块，并且输出答案的时候输出cnt+1就对了。

这个输入的思路真好

哈哈哈，感谢

有个疑问，dfs为啥不用pair，bfs用pair
啥时候用哪个方便呢？还是固定套路

dfs可以将坐标直接放在参数里，用pair的必要性不大，但是bfs是要将点放入队列中，自然使用pair便于存取

明白！

dfs解法，能不能在输入的时候就判断好‘@’的坐标？

咱们这里写的好像就先确定位置，再dfs吧，你是想要在dfs里做寻找’@’位置的这个操作吗？

大佬，递归不都应该由递归出口吗，这题为啥不用写递归出口

要全都是‘#’的话就不会继续向下dfs了，执行完也会自己返回的

问一下while读入的n||m什么意思啊

感觉应该是：最后读入为0 0的时候停止循环

对

我后来看了视频懂了，就是n，m只要有输入就不会结束，一直输入为真。0，0为假（应该）

应该是 n && m 好点吧

n && m只要有一个为0就会停止

诶，我的没报错。。。看来测试用例不在这里卡我

大佬为什么这个深搜完不需要将搜过的点恢复原样呢

因为你只需要搜索一次啊，破坏了也没有关系，只要保证第一次搜索的时候是合理的现场即可

谢大佬

举手之劳

这……怎么撞车了，我也是做一个dfs一个bfs……

哈哈哈，这类题的常用套路

这我也知道233333333333333333但是……我的题解可能要消失在茫茫题解海中了……hh

赞你一下，hhh

谢谢！

#include <bits/stdc++.h>

using namespace std;

char g[1001][1001];

bool st[1001][1001];

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

void dfs(int x,int y)
{
    g[x][y] = '#';
    cnt ++;
    for (int i = 0 ; i < 4 ; i ++)
    {
        int nx = x + dx[i] , ny = y + dy[i];
        if (0<=nx&&nx<n&&0<=ny&&ny<m&&g[nx][ny] == '.')
        {
            dfs(nx,ny);
        }
    }
    return;
}

int main ()
{
    while (scanf("%d%d",&n,&m) != EOF) {
        if (n==0||m == 0) break;
        for (int i = 0 ; i < n ; i ++)
            for (int j = 0 ; j < m ;j ++)
            {
                cin >> g[i][j];
            }
        for (int i = 0 ; i < n ; i ++)
            for (int j = 0 ; j < m ;j ++)
            {
                if (g[i][j] == '@')
                    dfs(i,j);
            }
        cout << cnt << endl;
        cnt = 0;
    }
    return 0;
}

大佬帮忙看一下我这个为什么不对吗

行列错了，m行n列

谢大佬了,这问题折腾我半天

多写写就好

Orz

tql

nb

hh,我是蒟蒻

dfs那样为什么到达黑色的瓷砖的最多呢，，不懂

他就是从起点开始走，找到黑色的就把当前标记为白色，让答案++，这样就能找到起点连着的所有黑色的了。

懂了！

好的