一、马的遍历
题目链接：P1443 马的遍历 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目要求：
有一个 n×m 的棋盘，在某个点 (x,y) 上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。
解题思路：
BFS板子，注意马走日，象棋的🐎
#include<bits/stdc++.h> using namespace std; const int N = 401; int dx[] = {2,-2,2,-2,-1,1,-1,1}; int dy[] = {1,1,-1,-1,2,2,-2,-2}; int a[N][N]; int b[N][N]; int n,m,x,y; struct node{ int x,y; }; void bfs(int x,int y) { queue<node>q; q.push({x,y}); a[x][y] = 1; b[x][y] = 0; while(q.size()) { node tt = q.front(); q.pop(); for(int i=0;i<8;i++) { int xxx = tt.x + dx[i]; int yyy = tt.y + dy[i]; if(xxx<1||xxx>n||yyy<1||yyy>m) { continue; } if(!a[xxx][yyy]) { a[xxx][yyy] = 1; b[xxx][yyy] = b[tt.x][tt.y]+1; q.push({xxx,yyy}); } } } } int main() { memset(b,-1,sizeof(b)); cin >> n >> m >> x >> y; bfs(x,y); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { printf("%-5d",b[i][j]); } cout<<endl; } return 0; }
二、砍树
题目链接：P1873 [COCI 2011/2012 #5] EKO / 砍树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目要求：
伐木工人 Mirko 需要砍 M 米长的木材。对 Mirko 来说这是很简单的工作，因为他有一个漂亮的新伐木机，可以如野火一般砍伐森林。不过，Mirko 只被允许砍伐一排树。
Mirko 的伐木机工作流程如下：Mirko 设置一个高度参数 H（米），伐木机升起一个巨大的锯片到高度 HH，并锯掉所有树比 H 高的部分（当然，树木不高于 HH 米的部分保持不变）。Mirko 就得到树木被锯下的部分。例如，如果一排树的高度分别为 20,15,10 和 17，Mirko 把锯片升到 15 米的高度，切割后树木剩下的高度将是 15,15,10 和 15，而 Mirko 将从第 1 棵树得到 5 米，从第 4 棵树得到 2 米，共得到 7 米木材。
Mirko 非常关注生态保护，所以他不会砍掉过多的木材。这也是他尽可能高地设定伐木机锯片的原因。请帮助 Mirko 找到伐木机锯片的最大的整数高度 H，使得他能得到的木材至少为 M 米。换句话说，如果再升高 1 米，他将得不到 M 米木材。
解题思路：
二分即可
#include<bits/stdc++.h> using namespace std; long long s=0,mid,l,maxx,a[1000001]; int main() { long long n,m; cin>>n>>m; for(int i=1;i<=n;i++) { cin>>a[i]; if(a[i]>maxx) { maxx = a[i]; } } while(l<=maxx) { mid=(l+maxx)/2; s=0; for(int i=1;i<=n;i++) { if(a[i]>mid) { s+=a[i]-mid; } } if(s<m) { maxx = mid - 1; } else { l = mid + 1; } } cout<<l-1; return 0; }
