字节8月21日 笔试第2题走迷宫，第4题 摇骰子比大小

#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;
}

#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;
}