网站建设资讯

NEWS

网站建设资讯

AcWing4510.寻宝!大冒险!(暴力枚举)-创新互联

题目如下:

在这里插入图片描述
在这里插入图片描述

博白网站制作公司哪家好,找成都创新互联公司!从网页设计、网站建设、微信开发、APP开发、响应式网站开发等网站项目制作,到程序开发,运营维护。成都创新互联公司于2013年成立到现在10年的时间,我们拥有了丰富的建站经验和运维经验,来保证我们的工作的顺利进行。专注于网站建设就选成都创新互联公司
输入样例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://cdweb.net/article/decggi.html