### 前言
一小时两道题， 吃完晚饭就整装待发准备做了，还是有点紧张的。想要做出一道就勉强混过去。
### 第一题 带牛去吃草多少种组合方式
小明带着n头牛 有m种颜色，每头牛都是互异的。
小明带任意头牛出去吃草。
请问有多少种组合？
种类太多 取模 1e9
1<= n <= 1e9, 1<= m <= 1e9
例：
输入：
3， 2
输出
27
举例
带0头 1
带1头 3 * 2
带2头 3 * 2 * 2
带3头 1 * 2 * 2 * 2
1 + 6 + 12 + 8 = 27
#### 自己猜测的题解
我当时看到这个就想到杨辉三角,当时没过，我当时忘了取模1e9但是不知道自己思路是否正确，因为我当时没思路就跳到第二题了。
``` cpp
#include <iostream>
#include <math.h>
using namespace std;
int main() {
long long n, m;
while(cin >> n >> m) {
cout << (long long) pow(m + 1, n) % 1e9 << endl;
}
}
```
### 第二题 迷宫中的最短路径
第一行输入，n,m,p 在（1，500）之间
随后输入n行m长度的字符串 C代表陆地， S代表海洋
随后p行按照bx, by, ex, ey
bx,by代表起点 ex,ey代表终点
输出起点到终点所需要最少体力
移动规则：
只能上下左右四个方向，
陆地到陆地消耗3体力，
海洋到海洋消耗2体力，
海洋到陆地或陆地到海洋消耗5体力，
输入：
4 4 2
CCCS
SSSS
CSCS
SSCC
1 1 4 3
3 1 1 3
输出：
13
14
#### 事后多花了半小时调通的题解
没机会扔进去测试一下对不对了。 感觉自己蛮代码的速度好慢呀。
``` cpp
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <queue>
using namespace std;
int xr[4] = {1, -1, 0, 0};
int yr[4] = {0, 0, 1, -1};
int n, m ,p;
bool inMat(int x, int y) {
return x>=0 && x < n && y >= 0 && y < m;
}
vector<vector<int>> bfs(int bx, int by, vector<string> &mat) {
queue<pair<int, int>> q;
vector<vector<int>> res(n, vector<int>(m , 0x3f3f3f));
q.push(make_pair(bx, by));
res[bx][by] = 0;
while(!q.empty()) {
pair<int, int> tmp = q.front();
q.pop();
int tx = tmp.first, ty = tmp.second;
for(int i = 0; i < 4 ;i ++) {
//判断是否在界内
if(inMat(tx+xr[i], ty + yr[i])) {
if(mat[tx][ty] == mat[tx + xr[i]][ty+yr[i]]) {
if(mat[tx][ty] == 'C') {
if(res[tx + xr[i]][ty+yr[i]] > res[tx][ty] + 3)
{
res[tx + xr[i]][ty+yr[i]] = res[tx][ty] + 3;
}
else {
//无更新， 跳过
continue;
}
}
if(mat[tx][ty] == 'S') {
if(res[tx + xr[i]][ty+yr[i]] > res[tx][ty] + 2)
{
res[tx + xr[i]][ty+yr[i]] = res[tx][ty] + 2;
}
else {
continue;
}
}
}
else {
if(res[tx + xr[i]][ty+yr[i]] > res[tx][ty] + 5)
{
res[tx + xr[i]][ty+yr[i]] = res[tx][ty] + 5;
}
else {
continue;
}
}
//有更新，进队
q.push(make_pair(tx+xr[i], ty + yr[i]));
}
}
}
return res;
}
int main(int argc, const char * argv[]) {
//cin >> n >> m >> p;
n = 4;
m = 4;
p = 2;
//vector<string> mat(n, "");
vector<string> mat;
mat.push_back("CCCS");
mat.push_back("SSSS");
mat.push_back("CSCS");
mat.push_back("SSCC");
// for(int i = 0; i < n; i++) {
// cin >> mat[i];
// }
// vector<vector<int>> be(p,vector<int>(4, 0) );
// for(int i = 0; i < p; i++) {
// for(int j = 0 ; j < 4; j++) {
// cin >> be[i][j];
// }
// }
vector<vector<int>> be = {{1, 1, 4, 3}, {3, 1, 1, 3}};
for(int i = 0 ; i < p; i++)
{
vector<vector<int>> dp(n, vector<int>(m , 0x3f3f3f));
// 题目中列为x， 行为y
dp = bfs(be[i][1] - 1, be[i][0] - 1, mat);
int ex = be[i][3], ey = be[i][2];
cout << dp[ex - 1][ey - 1]<< endl;
}
return 0;
}
```
### 后记
这次笔试我两道题都是0， 不知道会不会连面试的机会都没有， 每道题的题解也不知道对不对，有没有参加了并AC的大佬来指点一下迷津。刷题还得刷呀，code速度太慢了，思路没那么清晰，都是码一点想一点。我好菜呀，阿里好难。
全部评论
(2) 回帖