对于 90% 的数据, 保证随机生成.
对于 100% 的数据, 1<=N,M<=1000.
标签是 bfs,
我只会用 dfs.
下面是 dfs 爆搜.
- #include<iostream>
- #include<cstdio>
- #include<algorithm>
- #include<cstring>
- #include<cmath>
- using namespace std;
- int n,m,h[1002][1002],a,b,ans=1;
- int xx[5]={-1,1,0,0},yy[5]={0,0,1,-1};
- bool w[1002][1002],vis[1002][1002];
- void dfs(int x,int y)
- {
- vis[x][y]=1;
- for(int i=0;i<4;++i)
- {
- int dx=x+xx[i],dy=y+yy[i];
- if(dx<1||dx>n||dy<1||dy>m||w[dx][dy]==1||vis[dx][dy]==1)
- continue;
- if(h[dx][dy]<=h[x][y])
- {
- w[dx][dy]=1;
- ans++;
- }
- }
- for(int i=1;i<=n;++i)
- for(int j=1;j<=m;++j)
- if(w[i][j]==1&&!vis[i][j])
- dfs(i,j);
- }
- int main()
- {
- scanf("%d%d",&n,&m);
- for(int i=1;i<=n;++i)
- for(int j=1;j<=m;++j)
- scanf("%d",&h[i][j]);
- scanf("%d%d",&a,&b);
- w[a][b]=1;
- dfs(a,b);
- printf("%d",n*m-ans);
- }
- DFS75
这个也是 dfs, 还是很慢, 不过能过这道题,
对比一下思路吧.
- #include<cstdio>
- #include<iostream>
- using namespace std;
- int next[4][2]= {{0,1},{0,-1},{1,0},{-1,0}};
- int mp[1000][1000];
- int a[1000][1000];
- int n,m,sum=0;
- void dfs(int x,int y)
- {
- sum++;
- int t;
- t=mp[x][y];
- int i,j;
- for(i=0; i<4; i++)
- {
- int xx=x+next[i][0];
- int yy=y+next[i][1];
- if(xx<1||yy<1||xx>n||yy>m)
- continue ;
- if(mp[xx][yy]<=t&&a[xx][yy]==0)
- {
- a[xx][yy]=1;
- dfs(xx,yy);
- }
- }
- }
- int main()
- {
- int i,j;
- cin>>n>>m;
- for(i=1; i<=n; i++)
- for(j=1; j<=m; j++)
- cin>>mp[i][j];
- int x;
- int y;
- cin>>x>>y;
- a[x][y]=1;
- dfs(x,y);
- cout<<n*m-sum<<endl;
- return 0;
- }
- dfs AC
有人说这是个 bfs 的板子.
hh, 反正我不会.
狗子 zxl 又在外面发火了...
另附一份 bfsAC 代码.
自行理解.
- #include<iostream>
- #include<queue>
- using namespace std;
- struct point
- {
- int x,y;
- };
- int dir[4][2]= {{-1,0},{1,0},{0,-1},{0,1}};
- int lock[1001][1001] = {0};
- int a[1001][1001];
- int n, m, sum=0;
- void BFS(int x, int y)
- {
- queue <point> q;
- point now, next;
- now.x = x, now.y = y;
- q.push(now);
- lock[now.x][now.y] = -1;
- while(!q.empty())
- {
- now = q.front();
- for(int i=0; i<4; i++)
- {
- next.x = now.x + dir[i][0];
- next.y = now.y + dir[i][1];
- if(next.x<=0||next.y<=0||next.x>n||next.y>m) // 判断是否越界
- continue;
- if((a[next.x][next.y]<=a[now.x][now.y])&&lock[next.x][next.y]!=-1)// 如果洪水可以淹没, 且点没有访问过
- {
- q.push(next); // 该点入栈
- lock[next.x][next.y] = -1;
- }
- }
- q.pop();
- sum++;
- }
- }
- int main()
- {
- int p1, p2;
- cin>>n>>m;
- for(int i=1; i<=n; i++)
- {
- for(int j=1; j<=m; j++)
- cin>>a[i][j];
- }
- cin>>p1>>p2;
- BFS(p1,p2);
- cout<<n*m-sum<<endl;
- return 0;
- }
- bfs
来源: http://www.bubuko.com/infodetail-2638886.html