社区讨论
BFS过不了???
P1514[NOIP 2010 提高组] 引水入城参与者 4已保存回复 7
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 7 条
- 当前快照
- 1 份
- 快照标识符
- @mi6z10dg
- 此快照首次捕获于
- 2025/11/20 13:08 4 个月前
- 此快照最后确认于
- 2025/11/20 13:08 4 个月前
rt.
我的第一份代码是用BFS写的,7WA3TLE,广搜部分代码如下:
CPPvoid 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]);
}
}
}
}
调了整整一天后依然没有结果,于是在一位大佬的建议下把
CPPfor循环里的部分稍作修改后写成了DFS: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 条回复,欢迎继续交流。
正在加载回复...