目录
游游的you（贪⼼+模拟）
题目解析
讲解算法原理
编写代码
腐烂的苹果（多源BFS）
题目解析
讲解算法原理
编写代码
游游的you（贪⼼+模拟）
题目解析
1.题目链接：游游的you__牛客网
2.题目描述
游游现在有a个'y'，b个'o'，c个'u'，他想用这些字母拼成一个字符串。
三个相邻的字母是"you"可以获得2分，两个相邻的字母是"oo"，可以获得1分。
问最多可以获得多少分？
输入描述:
第一行一个整数qqq，代表询问次数。
接下来qqq行，每行三个正整数a,b,ca,b,ca,b,c，用空格隔开。
1≤q≤1051\leq q \leq 10^51≤q≤105
1≤a,b,c≤1091\leq a,b,c \leq 10^91≤a,b,c≤109
输出描述:
输出qqq行，代表每次询问的答案。
示例1
输入
3
1 1 1
2 3 2
1 5 2输出
2
4
5说明
第一次询问，可以拼出"you"，获得2分。
第二次询问，可以拼出"oyouyou"，获得4分。
第三次询问，可以拼出"uooooyou"，获得5分。
讲解算法原理
解法：
算法思路：
由题意得：
◦ you和oo是相互独⽴的；
◦ 但是you的分值更⾼，因此我们应该优先去拼凑you，然后再考虑oo
编写代码
c++算法代码：
#include <iostream>
using namespace std;
int main()
{int q;int a, b, c;cin >> q;while(q--){cin >> a >> b >> c;int x = min(a, min(b, c));cout << (x * 2 + max(b - x - 1, 0)) << endl;}return 0;
}java算法代码：
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main
{public static void main(String[] args) {Scanner in = new Scanner(System.in);int q = in.nextInt();int a, b, c;while(q-- != 0){a = in.nextInt(); b = in.nextInt(); c = in.nextInt();int x = Math.min(a, Math.min(b, c));System.out.println(x * 2 + Math.max(b - x - 1, 0));}}
}
腐烂的苹果（多源BFS）
题目解析
1.题目链接：腐烂的苹果_牛客题霸_牛客网
2.题目描述
描述
给定一个 n \times m \n×m 的网格，其中每个单元格中可能有三种值中的一个 0 , 1 , 2。
其中 0 表示这个格子为空、1 表示这个格子有一个完好的苹果，2 表示这个格子有一个腐烂的苹果。
腐烂的苹果每分钟会向上下左右四个方向的苹果传播一次病菌，并导致相邻的苹果腐烂。请问经过多少分钟，网格中不存在完好的苹果。如果有苹果永远不会腐烂则返回 -1
数据范围： 1 \le n , m \le 1000 \1≤n,m≤1000 ，网格中的值满足 0 \le val \le 2 \0≤val≤2
示例1
输入：
[[2,1,1],[1,0,1],[1,1,1]]
复制返回值：
4
复制
示例2
输入：
[[2,1,0],[1,0,1],[0,0,0]]
复制返回值：
-1
讲解算法原理
解法：
算法思路：
多源BFS问题，固定套路~
编写代码
c++算法代码：
class Solution
{int m, n;int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};bool vis[1010][1010] = { 0 };
public:int rotApple(vector<vector<int> >& grid) {m = grid.size(), n = grid[0].size();queue<pair<int, int>> q;for(int i = 0; i < m; i++)for(int j = 0; j < n; j++)if(grid[i][j] == 2)q.push({i, j});int ret = 0;while(q.size()){int sz = q.size();ret++;while(sz--){auto [a, b] = q.front();q.pop();for(int i = 0; i < 4; i++){int x = a + dx[i], y = b + dy[i];if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1
&& !vis[x][y]){vis[x][y] = true;q.push({x, y});}}}}for(int i = 0; i < m; i++)for(int j = 0; j < n; j++)if(grid[i][j] == 1 && !vis[i][j]) return -1;return ret - 1;}
};java算法代码：
import java.util.*;
public class Solution
{int[] dx = {0, 0, 1, -1};int[] dy = {1, -1, 0, 0};public int rotApple (ArrayList<ArrayList<Integer>> grid) {int m = grid.size();int n = grid.get(0).size();boolean[][] vis = new boolean[m][n];Queue<int[]> q = new LinkedList<>();for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(grid.get(i).get(j) == 2){q.add(new int[]{i, j});}}}int ret = 0;while(!q.isEmpty()){int sz = q.size();while(sz-- != 0){int[] t = q.poll();int a = t[0], b = t[1];for(int i = 0; i < 4; i++){int x = a + dx[i], y = b + dy[i];if(x >= 0 && x < m && y >= 0 && y < n && vis[x][y] == false&& grid.get(x).get(y) == 1){vis[x][y] = true;q.add(new int[]{x, y});}}}ret++;}// 判断剩余的苹果for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(grid.get(i).get(j) == 1 && !vis[i][j]){return -1;}}}return ret - 1; }
}
