AcWing4510.寻宝!大冒险!(暴力枚举)-创新互联
输入样例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();
}
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
本文题目:AcWing4510.寻宝!大冒险!(暴力枚举)-创新互联
分享网址:http://hbruida.cn/article/decggi.html