北京理工大学复试上机--2020

PS: 2020的是夏令营试题

1、题目：给你一个 m*n 大小的矩阵，每个点有 0，1，2 三种取值；0 代表障碍物，1代表白纸，2 代表墨滴。每一秒墨滴可以向其上下左右扩散，将四周的白纸染色，被染色之后的白纸可以继续向四周扩散，以此类推。问经过几秒，矩阵中所有的白纸都被染色。
如果可以，则输出扩散时间；
如果不可以，则输出FALSE。
输入: m n 的大小以及矩阵每个点的值
输出: 扩散时间或 FALSE
例如：
3 3
0 1 0
1 2 1
0 1 0
输出: 1

3 3
0 1 0
1 2 1
0 1 1
输出: 2

2 3
1 0 0
0 0 2
输出: False

#include <iostream>
#include <queue>
using namespace std;
int main() {
    int m, n;
    while (cin >> m >> n) {
        int arr[m][n];
        int temp = 0;
        queue<int> qx, qy;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                cin >> arr[i][j];
                if(arr[i][j] == 2) {
                    qx.push(i);
                    qy.push(j);
                }
                if(arr[i][j] == 1) temp++;
            }
        }
        int sec = 0;
        while(!qx.empty() && temp) {
            int size = qx.size();
            int dir[5] = {1, 0, -1, 0, 1};
            while(size--) {
                int x = qx.front();
                int y = qy.front();
                qx.pop();
                qy.pop();
                for(int i = 0; i < 4; i++) {
                    int dx = x + dir[i];
                    int dy = y + dir[i + 1];
                    if(dx < 0 || dx >= m || dy < 0 || dy >= n || arr[dx][dy] != 1) continue;
                    else {
                        arr[dx][dy] = 2;
                        temp--;
                        qx.push(dx);
                        qy.push(dy);
                    }
                }
            }
            sec++;
        }
        if (temp) cout << "False" << endl;
        else cout << sec << endl;
    }
    return 0;
}

2、输入三个字符串，问第三个字符串能否由前两个字符串多次重复组合形成。如果能，则输出前两个字符串各自的使用次数；如果不能，则输出 FALSE。
输入：三个字符串
输出：前两个字符串各自的次数或 FALSE
输入: aa bb bbaaaabbaa
输出: 3 2
输入: ab ba abbaaabaab
输出: FALSE
(注意特殊用例: aa aab aabaa 故递归)

#include <iostream>
using namespace std;
int cnt1 = 0, cnt2 = 0;
int flag[2][2];

bool sub(string s1, string s) {
    return s.substr(0, s1.length()) == s1;
}

bool dfsSub(string s1, string s2, string s, int p, int rem) {
    if(rem == s1.length() || rem == s2.length()) {
        if(sub(s1, s.substr(p, rem))) {
            cnt1++;
            return true;
        }
        if(sub(s2, s.substr(p, rem))) {
            cnt2++;
            return true;
        }
        return false;
    }
    if(sub(s1, s.substr(p, rem)) && sub(s2, s.substr(p, rem))) {
        cnt1++;
        p += s1.length();
        rem -= s1.length();
        if(dfsSub(s1, s2, s, p, rem)) return true;
        else {
            p -= s1.length();
            rem += s1.length();
            cnt1--;
            cnt2++;
            p += s2.length();
            rem -= s2.length();
            if(dfsSub(s1, s2, s, p, rem)) return true;
            else {
                cnt2--;
                return false;
            }
        }
    }
    else if(sub(s1, s.substr(p, rem))) {
        cnt1++;
        p += s1.length();
        rem -= s1.length();
        return dfsSub(s1, s2, s, p, rem);
    }
    else if(sub(s2, s.substr(p, rem))) {
        cnt2++;
        p += s2.length();
        rem -= s2.length();
        return dfsSub(s1, s2, s, p, rem);
    }
    else return false;
}


int main() {
    string s, s1, s2;
    while(cin >> s1 >> s2 >> s) {
        int l = s.length();
        if(dfsSub(s1, s2, s, 0, l)) {
            cout << cnt1 << "  " << cnt2 << endl;
        }
        else cout << "FALSE" << endl;
        cnt1 = 0;
        cnt2 = 0;
    }
    return 0;
}

PS: 暂时是更新完了，综合面试也是一个大头，都抓紧吧，尽量不手生，多看多练加油！！！！ Fighting！！！（别忘了前面未完善的！！）