练习题目如下
1
2
3
4
5
6
7
编程题1
【算法分析】 可以发现如果一个格子中的一条边是周长的一部分,那么要么它是边界,要么它的两边是 1 和 0。因此可以遍历网格,找到每个陆地的格子,并判断它的四条边哪些是周长的一部分。 【参考代码】 #include<bits/stdc++.h> using namespace std; int a[1009][1009]; int dir[4][2] = { -1,0,0,1,1,0,0,-1 }; int main() { int n, m; cin >> n >> m; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) cin >> a[i][j]; } int ans = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (a[i][j]) { for (int k = 0; k < 4; k++) { int x = i + dir[k][0], y = j + dir[k][1]; if (x<1 || x>n || y<1 || y>m || !a[x][y]) ans++; } } } } cout << ans; return 0; }View Code
编程题2
广搜解决
【算法分析】 从 Q 到 W 最少需要的步数,可以考虑广搜。广搜的每一步都是去选择四位数当中的某一位进行改变,同时又需要改变之后的数是素数。如果在广搜的过程中判断素数,那时间复杂度会很高,因此可以先预处理出每个数是不是素数(这里用的是埃氏筛,当然用 nsqrt(n) 的算法时间也是允许的)。 【参考代码】 #include<bits/stdc++.h> using namespace std; const int maxn = 1e4 + 9; bool prime[maxn]; int vis[maxn]; //vis[i]表示从Q到i需要的次数 void init() { //埃氏筛素数 prime[1] = 1; for (int i = 2; i < maxn; i++) { for (int j = 2 * i; j < maxn; j += i) prime[j] = 1; } } int bfs(int Q, int W) { memset(vis, -1, sizeof(vis)); //用-1表示从Q到不能到i,多组数据,每次需要初始化 queue<int> q; q.push(Q); vis[Q] = 0; //Q到Q的次数是0 while (q.size()) { int r = q.front(); q.pop(); if (r == W) return vis[W]; for (int i = 0; i < 10; i++) { //个位 int tm = r - r % 10 + i; if (prime[tm] == 0 && vis[tm] == -1 && tm >= 1000) { //题目说改变后的数要在1000~9999范围内 q.push(tm); vis[tm] = vis[r] + 1; } //十位 tm = r - (r / 10 % 10) * 10 + i * 10; if (prime[tm] == 0 && vis[tm] == -1 && tm >= 1000) { q.push(tm); vis[tm] = vis[r] + 1; } //百位 tm = r - (r / 100 % 10) * 100 + i * 100; if (prime[tm] == 0 && vis[tm] == -1 && tm >= 1000) { q.push(tm); vis[tm] = vis[r] + 1; } //千位 tm = r - (r / 1000 % 10) * 1000 + i * 1000; if (prime[tm] == 0 && vis[tm] == -1 && tm >= 1000) { q.push(tm); vis[tm] = vis[r] + 1; } } } return 0; } int main() { init(); int _; cin >> _; while (_--) { int Q, W; cin >> Q >> W; cout << bfs(Q, W) << '\n'; } return 0; }View Code
本节课作业讲解视频
链接:https://pan.baidu.com/s/1hd3HG-NafZNQVV08tkQaRA?pwd=0c9g
提取码:0c9g
标签:10,12,vis,U5,C++,int,tm,&&,1000 From: https://www.cnblogs.com/jayxuan/p/17937921