AcWing 1106. 山峰和山谷
原题链接
中等
作者:
cht
,
2020-06-25 13:11:17
,
所有人可见
,
阅读 894
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, h[N][N];
pair<int, int> q[N * N];
bool st[N][N];
void Flood_Fill(int x, int y, bool &res1, bool &res2)
{
int hh = 0, tt = -1;
q[ ++ tt] = {x, y};
st[x][y] = true;
while(hh <= tt)
{
pair<int, int> t = q[hh ++];
for(int i = t.first - 1; i <= t.first + 1; i ++)
for(int j = t.second - 1; j <= t.second + 1; j ++)
{
if(i == t.first && j == t.second) continue;
if(i < 0 || i >= n || j < 0 || j >= n) continue;
if(h[i][j] != h[t.first][t.second])
{
if(h[i][j] > h[t.first][t.second]) res1 = true;
else res2 = true;
}
else if(!st[i][j])
{
q[ ++ tt] = {i, j};
st[i][j] = true;
}
}
}
}
pair<int, int> bfs()
{
int ans1 = 0, ans2 = 0;
for(int i = 0; i < n; i ++)
for(int j = 0; j < n; j ++)
if(!st[i][j])
{
bool res1 = false, res2 = false;
Flood_Fill(i, j, res1, res2);
if(!res1) ans1 ++;
if(!res2) ans2 ++;
}
pair<int, int> alls = {ans1, ans2};
return alls;
}
int main()
{
scanf("%d", &n);
for(int i = 0; i < n; i ++)
for(int j = 0; j < n; j ++)
scanf("%d", &h[i][j]);
pair<int, int> res = bfs();
cout << res.first << ' ' << res.second << endl;
return 0;
}
dfs为什么会超时呀
因为dfs会超时。。。