问一下为什么这样写bfs不对

P1162 填涂颜色

天马行空mz @ 2022-03-30 15:37:18

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define maxn 2000
int nt[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//右下左上
int n,f[maxn][maxn];
int vis[maxn][maxn];
struct qe
{
    int x,y;
};
queue<qe> q;
void bfs(int x,int y)
{
    qe start,next;
    start.x=x;
    start.y=y;
    q.push(start);
    while(!q.empty())
    {
        start=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            next.x=start.x+nt[i][0];
            next.y=start.y+nt[i][1];
            if(next.x<1||next.x>n||next.y<1||next.y>n)
                continue;//不满足条件跳过取
            if(vis[x][y]==1||f[next.x][next.y]==1)
                continue;
            f[next.x][next.y]=2;
            vis[next.x][next.y]=1;
            q.push(next);
        }
    }
}

by _Harry_Potter_ @ 2022-03-30 15:46:13

其实用dfs就可以啦 dfs比bfs简便多了


by zxy123bc @ 2022-03-30 15:47:46

@天马行空mz 建议把全代码放出来

然后说明下你认为的问题在哪


by zxy123bc @ 2022-03-30 15:48:53

@Chenzr

dfs慢

bfs快但是占得内存多

建议两个都会


by 天马行空mz @ 2022-03-30 15:55:59

@zxy123bc 主函数就写了一个输入一个输出,直接bfs(0,0)来计算的。


by zxy123bc @ 2022-03-30 16:06:14

这里:

if(vis[x][y]==1||f[next.x][next.y]==1)continue;

vis的下标不对吧(也许)


by zxy123bc @ 2022-03-30 16:06:28

@天马行空mz


by _Harry_Potter_ @ 2022-03-30 16:24:02

@zxy123bc bfs的确快 但是这道题用不到 在考试的时候浪费时间 需要的时候再用bfs


by 天马行空mz @ 2022-03-30 17:13:22

@zxy123bc 确实是这样,问题解决了,谢谢谢谢qwq


|