AcWing 3371. 舒适的奶牛
原题链接
简单
作者:
胡歌-此生不换
,
2022-05-09 23:13:33
,
所有人可见
,
阅读 244
//时间复杂度:O(N)
// 思路:把每头奶牛存到bool数组里
// 当一头奶牛被添加时 算上它本身 共计会更新5头奶牛的状态
// 所以在添加这头奶牛前 可以先计算出舒适的奶牛的数量
// 添加后 再次计算 根据差值得出ans并输出
#include <iostream>
#include <algorithm>
// #include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int a[N][N];
int n;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int istrue(int x, int y)
{
if(a[x][y] == 0) return 0;
int cnt = 0;
for(int i = 0; i < 4; i++)
{
int x1 = x + dx[i], y1 = y + dy[i];
if(x1 >= 0 && x1 <= n && y1 >= 0 && y1 <= n && a[x1][y1] == 1)
cnt++;
}
if(cnt == 3) return 1;
else return 0;
}
int main(void)
{
cin >> n;
int ans = 0;
int k = n;
while(k--)
{
int x, y;
cin >> x >> y;
for(int i = 0; i < 4; i++)
{
int x1 = x + dx[i], y1 = y + dy[i];
if(x1 >= 0 && x1 <= n && y1 >= 0 && y1 <= n)
ans -= istrue(x1, y1);
}
a[x][y] = 1;
for(int i = 0; i < 4; i++)
{
int x1 = x + dx[i], y1 = y + dy[i];
if(x1 >= 0 && x1 <= n && y1 >= 0 && y1 <= n)
ans += istrue(x1, y1);
}
ans += istrue(x, y);
cout << ans << endl;
}
return 0;
}
// 错误代码 :
//时间复杂度:O(N)
// 思路:把每头奶牛存到bool数组里
// 当一头奶牛被添加时 算上它本身 共计会更新5头奶牛的状态
// 所以在添加这头奶牛前 可以先计算出舒适的奶牛的数量
// 添加后 再次计算 根据差值得出ans并输出
// #include <iostream>
// #include <algorithm>
// using namespace std;
// const int N = 1010;
// int a[N][N];
// int n;
// int v(int i, int j)
// {
// return a[i - 1][j] + a[i + 1][j] + a[i][j - 1] + a[i][j + 1];
// }
// int main(void)
// {
// cin >> n;
// while(n--)
// {
// int c, b;
// cin >> c >> b;
// a[c + 1][b + 1] = 1;
// int res = 0;
// for(int i = 1; i < 1003; i++)
// {
// for(int j = 1; j < 1003; j++)
// {
// if(a[i][j] == 0) continue;
// if(a[i][j] == 1 && v(i, j) == 3) res++;
// }
// }
// cout << res << endl;
// }
// return 0;
// }
最后再计算加入的牛奶是不是舒适牛奶
加入牛奶之后为什么又要加一下周围舒适牛奶的数量 : 因为加入牛奶后,对周围牛奶舒适情况会变化,所以要加一下