2022-09-22-微软二面-45min

https://www.nowcoder.com/discuss/1060275

自我介绍，讲研二的论文，对研一做的高可靠并行匹配模型感兴趣问了一下，二十几分钟吧。

题目是个bfs扩展步数。空位置为0，好橘子为1，坏橘子为2，每一步坏橘子往4个方向上传播把好的变坏掉的。
说没什么错，能不能优化一下，我说是Omn了，
后说时间空间都做得不错，这个next队列能不能不用，于是就有了下面的注释。
说行没什么了，没要反问了。。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

#define _for(i,a,b) for(int i=a;i<b;i++)

inline bool valid(int i, int j, int n, int m){
    return 0<=i&&i<n&&0<=j&&j<m;
}

pair<int,int> stableStepNum(vector<vector<int>> a){
    int ans=0, n=a.size(),m=a[0].size(),ngood=0;
    queue<pair<int,int>> q;
    _for(i,0,n){
        _for(j,0,m){
            if(a[i][j]==2){
                q.push({i,j});
                // a[i][j]=-1; // ?
            }else if(a[i][j]==1)
                ngood++;
        }
    }
    int dir[5]={0,1,0,-1,0};
    while(!q.empty()){
        queue<pair<int,int>> next;
        // int nq=q.size();
        // _for(k,0,nq){
        //     q.push({});
        // }
        while(!q.empty()){
            auto t = q.front();
            q.pop();
            for(int i=0;i<4;i++){
                int nx=t.first+dir[i],ny=t.second+dir[i+1];
                if(valid(nx,ny,n,m)&&a[nx][ny]==1){
                    next.push({nx,ny});
                    a[nx][ny]=2;
                    ngood--;
                }
            }
        }
        ans++;
        q=next;
    }
    return {ans, ngood};
}

int main() {
    // you can write to stdout for debugging purposes, e.g.
    std::cout << "This is a debug message" << std::endl;

    return 0;
}