Hzj201014 @ 2024-02-02 16:13:51
#include<bits/stdc++.h>
using namespace std;
#pragma G++ optimize(2)
char dt[1005][1005];
int n,m,x,y,ans[405][405],t,ditu[1005][1005];
int d[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
struct node{
int x,y,r;
};
queue<node>que;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i = 1;i <= n;i++){
for(int j = 1;j <= n;j++){
cin>>dt[i][j];
ditu[i][j] = dt[i][j] - '0';
}
}
for(int i = 1;i <= n;i++){
for(int j = 1;j <= n;j++){
ans[i][j] = -1;
}
}
for(int k = 1;k <= m;k++){
t = 0;
cin>>x>>y;
node a = {x,y,0};
que.push(a);
ans[x][y] = 0;
while(!que.empty()){
int X = que.front().x,Y = que.front().y;
for(register int i = 0;i < 4;i++){
int newx = X + d[i][0],newy = Y + d[i][1];
if(newx >= 1 && newx <= n && newy >= 1 && newy <= n&& ans[newx][newy] == -1){
a = {newx,newy,que.front().r + 1};
que.push(a);
ans[newx][newy] = que.front().r + 1;
}
}
que.pop();
}
for(int i = 1;i <= n;i++){
for(int j = 1;j <= n;j++){
if(ans[i][j] != -1){
t++;
}
}
}
cout<<t<<'\n';
}
return 0;
}
by yangzishuo0418 @ 2024-02-09 12:35:31
你有没有想过每次
by yangzishuo0418 @ 2024-02-09 12:36:48
没清空的话你没法判断那个点你有没有踩过
by yangzishuo0418 @ 2024-02-09 12:38:18
应该在第 memset(ans,-1,sizeof a)
(尽管这样可能会超时)
by masonxiong @ 2024-02-09 22:40:32
显然,这个程序复杂度就不对
如果迷宫是一个所有格子互相可达的图,那么一次搜索的时间可以达到
鉴于
而且,你每次 BFS 时的 ans
数组并未初始化,导致结果肯定就不对,直接 WA
另,你需要知道,register
关键字已经弃用了,而 Luogu 有 #pragma G++ optimize(2)
没必要,std::queue
又是对 std::deque
的封装,后者常数极大,解绑优化在小规模输入时也没有用处,你这优化了也和没优化一样
正确的解法是,鉴于此迷宫可被看为一个无向图,也就是说,若 A 能到 B,则 B 一定能到 A(显然),那么一个连通分量内的答案都是相等的,也就是这个联通分量的大小。
求解这个可以使用 Tarjan
算法,当然这太大材小用,我们只需要进行多次 DFS 查找全部连通分量即可。
此算法时间复杂度可以达到