字节8月21日 笔试第2题走迷宫，第4题 摇骰子比大小
第二题用了dfs（好像用bfs会更简洁）
#include<vector>
using namespace std;
// #include<algorithm>
#include<iostream>
// write your code in C++ (C++14 (g++ 6.2.0))
int ans = 1;
bool dfs(vector<vector<char>> &maze, vector<vector<int>> &visited, int i, int j, int m, int n) {
if(i<0 || i>=m || j<0 || j>=n) { //碰到边
return 0;
}
if(maze[i][j] == 'O') {
return 1;
}
if(maze[i][j] == 'N') { //碰到走不通的路
return 0;
}
if(visited[i][j] == 1) return 0; //已经走过的路
if(visited[i][j] == 2) return 0; //传送带
bool res;
switch(maze[i][j]){
case '.':
visited[i][j] = 1;
res = dfs(maze, visited, i+1, j, m, n) || dfs(maze, visited, i-1, j, m, n)
|| dfs(maze, visited, i, j+1, m, n) || dfs(maze, visited, i, j-1, m, n);
break;
case 'R':
visited[i][j] = 2;
res = dfs(maze, visited, i, j+1, m, n);
break;
case 'L':
visited[i][j] = 2;
res = dfs(maze, visited, i, j-1, m, n);
break;
case 'U':
visited[i][j] = 2;
res = dfs(maze, visited, i-1, j, m, n);
break;
case 'D':
visited[i][j] = 2;
res = dfs(maze, visited, i+1, j, m, n);
break;
default:
res = 0;
break;
}
if(res){ //走的通的路标记为‘O’
maze[i][j] = 'O';
ans++;
visited[i][j] = 0;
cout<<i<<"\t"<<j<<"\t"<<int(res)<<"\t"<<ans<<endl;
return 1;
}else if(visited[i][j]==2){ //走不通的路标记为‘N’,
maze[i][j] = 'N'; //res==0的时候如果是在‘.’上不能判定走不通，因为实际情况可以往回走
// visited[i][j] = 0;
return 0;
}else{
visited[i][j] = 0;
return 0;
}
}
int main(){
//输入操作略
// int m, n;
// cin>>m>>n;
// vector<vector<int>> maze(m,n);
//测试用例
int m = 5, n = 5;
vector<vector<char>> maze = {{'.', '.', '.', '.', '.'},
{'.', 'R', 'R', 'D', '.'},
{'.', 'U', '.', 'D', 'R'},
{'.', 'U', 'L', 'L', '.'},
{'.', '.', '.', '.', 'O'}};
// int m = 3, n = 4;
// vector<vector<char>> maze = {{'O', 'U', '.', '.'},
// {'L', '.', '.', '.'},
// {'.', '.', '.', '.'}};
// maze[m-1][n-1] = 'O';
vector<vector<int>> visited(m, vector<int>(n,0));
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(maze[i][j] != 'O' && maze[i][j]!='N'){
dfs(maze, visited, i, j, m, n);
}
}
}
cout << m*n-ans<< endl;
return 0;
}
第4题大致思路：用an，bn表示两个数组大小，suma，sumb表示数组中所有元素总和，如果摇骰子每次为结果都是1，那么结果就是数组大小，如果每次都是最大值，那么结果就是数组所有元素总和。
对于每个骰子，每一个面朝上概率是一样的，这意味着每个人的每个结果点数和的概率都是一样的，所以只要统计每组数所有可能的总和的个数就可以最后算出概率，
例如如果a = {8}， 那么可能有8种和即1~8，每种和只有一种情况，b = {2, 3, 4}，就可能有2+3+4 -3+1= 7种和（最小为3对应每个骰子恰好都是1朝上，最大是9对应每个骰子都恰好是最大值朝上）每种和对应的情况数可能不同，比如和为4的情况有3种，分别是[1, 1, 2], [1, 2, 1], [1, 1, 2]，需要用dfs统计每个和的情况次数 。
ps：因为要算a组数赢的概率，所以最后比较的是a的所有情况总和中大于b的情况，这里就有剪枝的空间了： 如果 a的个数都比b的总和要大了那肯定赢，返回1.0，反之肯定输，返回0.0。
相应的，用dfs计数的时候也只需要统计最后需要比较的情况，所以dfs也可以剪枝，这里懒得写了。。。
#include<vector>
using namespace std;
#include<algorithm>
#include<iostream>
#include<unordered_map>
#include<iomanip>
// write your code in C++ (C++14 (g++ 6.2.0))
//dfs计算掷完一组骰子每个值可能出现的次数
void dfs(vector<int> &A, unordered_map<int, int> &hashm, int cursum, int n, int depth) {
if(depth == n) {
hashm[cursum]++;
return ;
}
for(int i=1; i<=A[depth]; i++){
cursum += i;
// cout<<cursum<<":"<<hashm[cursum]<<"\t";
dfs(A, hashm, cursum, n, depth+1);
cursum -= i;
}
}
int main(){
// int an, bn;
// cin>>an>>bn;
// vector<int> A(an), B(bn);
int an = 1, bn = 3;
vector<int> A = {8}, B = {2, 3, 4};
int suma = 0, sumb = 0;
double p_a = 1.0, p_b = 1.0;
for(int i=0; i<an; i++) {
// cin>>A[i];
suma+=A[i];
p_a *= 1.0/A[i];
}
for(int i=0; i<bn; i++){
// cin>>B[i];
sumb+=B[i];
p_b *= 1.0/B[i];
}
if(suma<=bn){
cout << setprecision(3) << fixed << 0.0<< endl; //控制小数位输出
return 0;
}
if(sumb<an){
cout << setprecision(3) << fixed << 1.0<< endl; //控制小数位输出
return 0;
}
unordered_map<int, int> hash_a;
unordered_map<int, int> hash_b;
dfs(A, hash_a, 0, an, 0);
dfs(B, hash_b, 0, bn, 0);
int start, end;
if(bn>an) start = bn+1;
else start = an;
end = suma;
// cout<<endl;
// cout<<an<<"\t"<<suma<<"\n"<<bn<<"\t"<<sumb<<endl;
// cout<<"p:"<<p_a<<"\t"<<p_b<<endl;
// cout<<"start:"<<start<<"\t"<<end<<endl;
double ans = 0.0;
for(int i=start; i<=end; i++){
for(int j=bn; j<i; j++){
ans += hash_a[i]*p_a*hash_b[j]*p_b;
// cout<<i<<":"<<hash_a[i]<<"\t"<<j<<":"<<hash_b[j]<<endl;
}
// cout<<ans<<endl;
}
cout << setprecision(3) << fixed << ans<< endl;
}
查看24道真题和解析
