社区讨论

BFS过不了???

P1514[NOIP 2010 提高组] 引水入城参与者 4已保存回复 7

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
7 条
当前快照
1 份
快照标识符
@mi6z10dg
此快照首次捕获于
2025/11/20 13:08
4 个月前
此快照最后确认于
2025/11/20 13:08
4 个月前
查看原帖
rt.
我的第一份代码是用BFS写的,7WA3TLE,广搜部分代码如下:
CPP
void BFS(int x,int y)
{
    queue<pair<int,int>> q;
    q.push(make_pair(x,y));
    while(!q.empty()){
        auto now=q.front();
        q.pop();
        vis[now.first][now.second]=true;
        for(int i=1;i<=4;i++){
            int xi=now.first+fx[i][0];
            int yi=now.second+fx[i][1];
            if(xi>0&&xi<=n&&yi>0&&yi<=m&&a[x][y]>a[xi][yi]){
                if(!vis[xi][yi]) q.push(make_pair(xi,yi));
                l[x][y]=min(l[x][y],l[xi][yi]);
                r[x][y]=max(r[x][y],r[xi][yi]);
            }
        }
    }
}
调了整整一天后依然没有结果,于是在一位大佬的建议下把for循环里的部分稍作修改后写成了DFS:
CPP
void DFS(int x,int y)
{
	vis[x][y]=true;
	for(int i=1;i<=4;i++){
		int xi=x+fx[i][0];
		int yi=y+fx[i][1];
		if(xi>0&&xi<=n&&yi>0&&yi<=m&&a[x][y]>a[xi][yi]){
			if(!vis[xi][yi]) DFS(xi,yi);
			l[x][y]=min(l[x][y],l[xi][yi]);
           	r[x][y]=max(r[x][y],r[xi][yi]);
		}
	}
}
其余部分没有任何改变。
然后就AC了???
求指导这是为什么?

回复

7 条回复,欢迎继续交流。

正在加载回复...