目录
kotori和⽓球（组合数学）
题目解析
讲解算法原理
编写代码
⾛迷宫（BFS）
题目解析
讲解算法原理
编写代码
kotori和⽓球（组合数学）
题目解析
1.题目链接：登录—专业IT笔试面试备考平台_牛客网
2.题目描述
题目描述
kotori最近迷上了摆气球的游戏。她一共有n种气球，每种气球有无数个。她要拿出若干个气球摆成一排。
但是，由于气球被施放了魔法，同样种类的气球如果相邻会发生爆炸，因此若两个相邻的气球种类相同被视为不合法的。
kotori想知道，摆成一排m个一共有多少种不同的方案？
由于该数可能过大，只需要输出其对109取模的结果。
输入描述:
输入仅有一行，为两个整数n和m(1≤n,m≤100)
输出描述:
输出一个整数，为方案数对109取模的结果。
示例1
输入
3 2
3 2
输出
6
6
讲解算法原理
解法：
算法思路：
简单的排列组合问题，结果等于n与m个n-1的乘积。
编写代码
c++算法代码：
#include <iostream>
using namespace std;
const int MOD = 109;
int main()
{int n, m;cin >> n >> m;int ret = n;for(int i = 0; i < m - 1; i++){ret = ret * (n - 1) % MOD;}cout << ret << endl;return 0;
}java算法代码：
import java.util.*;
public class Main
{public static int MOD = 109;public static void main(String[] args){Scanner in = new Scanner(System.in); int n = in.nextInt(), m = in.nextInt(); int ret = n; for(int i = 0; i < m - 1; i++) { ret = ret * (n - 1) % MOD; }System.out.println(ret);}
}⾛迷宫（BFS）
题目解析
1.题目链接：走迷宫_牛客题霸_牛客网
2.题目描述
描述
给定一个n\times mn×m的网格，在网格中每次在不超过边界的情况下可以选择向上、向下、向左、向右移动一格。网格中的一些格子上放置有障碍物，放有障碍物的格子不能到达。求从(x_s,y_s)(xs,ys)到(x_t,y_t)(xt,yt)最少的移动次数。若不能到达，输出-1−1。
输入描述：
第一行输入两个整数n,mn,m (1\le n, m \le 10001≤n,m≤1000)，表示网格大小。
第二行输入四个整数x_s,y_s,x_t,y_txs,ys,xt,yt (1\le x_s, x_t \le n1≤xs,xt≤n, 1\le y_s, y_t \le m1≤ys,yt≤m)，表示起点和终点的坐标。
接下来的nn行，每行输入一个长度为mm的字符串。其中，第ii行第jj个字符表示第ii行第jj列的格子上的障碍物情况，若字符为'*'，则格子上有障碍物，若字符为'.'，则格子上没有障碍物。
保证起点不存在障碍物。输出描述：
输出一行一个整数，表示从(x_s,y_s)(xs,ys)到(x_t,y_t)(xt,yt)最少的移动次数。
示例1
输入：
5 5
1 1 5 5
.....
****.
.....
**.**
.....输出：
12
示例2
输入：
5 5
1 1 4 5
.....
****.
.....
**.**
.....输出：
-1
示例3
输入：
5 5
1 1 5 5
.....
****.
.....
*****
.....输出：
-1
讲解算法原理
解法：
算法思路：
简单bfs应⽤题。
编写代码
c++算法代码：
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1010;
int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};
int n, m;
int x1, y1, x2, y2;
char arr[N][N];int dist[N][N]; // [i, j] 位置是否已经搜索过，以及到达 [i, j] 位置的最短距离
int bfs()
{if(arr[x2][y2] == '*') return -1;memset(dist, -1, sizeof dist); // 表⽰还没开始搜索 queue<pair<int, int>> q; q.push({x1, y1}); dist[x1][y1] = 0;while(q.size()){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 >= 1 && x <= n && y >= 0 && y <= m && arr[x][y] == '.' && dist[x][y] == -1){q.push({x, y}); dist[x][y] = dist[a][b] + 1; if(x == x2 && y == y2) return dist[x2][y2]; }}}return -1;
}
int main()
{cin >> n >> m >> x1 >> y1 >> x2 >> y2; for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){cin >> arr[i][j];}}cout << bfs() << endl;return 0;
}java算法代码：
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main
{public static int N = 1010; public static int[] dx = {0, 0, 1, -1}; public static int[] dy = {-1, 1, 0, 0};public static int n, m, x1, y1, x2, y2; public static char[][] arr = new char[N][N];public static int[][] dist = new int[N][N]; // 标记当前位置有没有搜索过，以及⾛
到该位置时候的最短步数public static int bfs(){if(arr[x2][y2] == '*') return -1;for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++)dist[i][j] = -1; // 表明刚开始每个位置都没有搜索过 Queue<int[]> q = new LinkedList<>(); q.add(new int[]{x1, y1}); dist[x1][y1] = 0;while(!q.isEmpty()){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 >= 1 && x <= n && y >= 1 && y <= m && arr[x][y] == '.' && dist[x][y] == -1){q.add(new int[]{x, y}); dist[x][y] = dist[a][b] + 1; if(x == x2 && y == y2) { return dist[x][y]; }}}}return -1;}public static void main(String[] args) {Scanner in = new Scanner(System.in); n = in.nextInt(); m = in.nextInt(); x1 = in.nextInt(); y1 = in.nextInt(); x2 = in.nextInt(); y2 = in.nextInt(); for(int i = 1; i <= n; i++){String tmp = in.next(); for(int j = 1; j <= m; j++) { arr[i][j] = tmp.charAt(j - 1); }}System.out.println(bfs());}
}