AcWing 4510. 寻宝!大冒险!(暴力枚举)
题目如下:
输入样例1:
5 100 2
0 0
1 1
2 2
3 3
4 4
0 0 1
0 1 0
1 0 0
输出样例1:
3
样例 1 1 1 解释
绿化图上 ( 0 , 0 ) (0,0) (0,0)、 ( 1 , 1 ) (1,1) (1,1) 和 ( 2 , 2 ) (2,2) (2,2) 三处均可能埋有宝藏。
输入样例2:
5 4 2
0 0
1 1
2 2
3 3
4 4
0 0 0
0 1 0
1 0 0
输出样例2:
0
样例 2 2 2 解释
如果将藏宝图左下角与绿化图 ( 3 , 3 ) (3,3) (3,3) 处对应,则藏宝图右上角会超出绿化图边界,对应不成功。
题解 or 思路:
题目中说:
特别地,藏宝图左下角位置一定是一棵树,即
A
[
x
]
[
y
]
=
B
[
0
]
[
0
]
=
1
A[x][y]=B[0][0]=1
A[x][y]=B[0][0]=1,表示了宝藏埋藏的位置。
所以,我们可以枚举左下角, 然后检查是否合法,如果合法答案 + 1 + 1 +1
AC 代码如下:
const int N = 1009;
int n, l, s;
int x[N], y[N], b[N][N];
void solve()
{
cin >> n >> l >> s;
for (int i = 1; i <= n; i++)
cin >> x[i] >> y[i];
int one = 0;
for (int i = s; i >= 0; i--)
for (int j = 0; j <= s; j++)
cin >> b[i][j], one += b[i][j];
int ans = 0;
for (int i = 1; i <= n; i++)
{
if (x[i] + s > l || y[i] + s > l)
continue;
int cnt = 0;
for (int j = 1; j <= n; j++)
{
if (cnt == -1)
break;
if (x[j] >= x[i] && x[j] <= x[i] + s && y[j] >= y[i] && y[j] <= y[i] + s)
{
b[x[j] - x[i]][y[j] - y[i]] ? cnt++ : cnt = -1;
}
}
ans += (cnt == one ? 1 : 0);
}
cout << ans << '\n';
}
int main()
{
solve();
}