大疆笔试 大疆笔试题 0818

无人机

#include <iostream>
#include <vector>


using namespace std;

class Solution {
public:

    /* Write Code Here */
    int ans = 1, n = 0, m = 0;
    vector<vector<int>> g;  // 保存图
    vector<vector<vector<bool>>> std; // 保存该点，某方向 是否访问过了
    vector<vector<bool>> st; // 保存该点是否访问过了

    vector<int> dx = {0, 1, 0, -1}, dy = {1, 0 ,-1 , 0};

    void dfs(int x, int y, int d)
    {
        for (int i = 0; i < 4; i++) {
            int nd = (d + i) % 4; // 方向要和上一个方向保持一致
            int nx = x + dx[nd] , ny = y + dy[nd];
            if (nx > -1 && nx < n && ny > -1 && ny < m && !g[nx][ny]) { // 合法坐标，并且可访问
                if (!st[nx][ny])  ans++; // 统计过了 就不需要统计了
                st[nx][ny] = true;
                if (!std[x][y][nd]) { // 当前方向没有被访问过，防止死循环
                    std[x][y][nd] = true;
                    dfs(nx , ny, nd);
                }
                return;
            }
        }
    }
    int numberOfPatrolBlocks(vector < vector < int > > block) {
        n = block.size(), m = block[0].size();
        g = block;
        st = vector<vector<bool>> (n, vector<bool>(m));
        std = vector<vector<vector<bool>>> (n, vector<vector<bool>> (m, vector<bool>(4)));
        ans = 1;
        st[0][0] = true;
        dfs(0, 0, 0);
        return ans;
    }
};
int main() {
    int res;

    int block_rows = 0;
    int block_cols = 0;
    cin >> block_rows >> block_cols;
    vector< vector < int > > block(block_rows);
    for(int block_i=0; block_i<block_rows; block_i++) {
        for(int block_j=0; block_j<block_cols; block_j++) {
            int block_tmp;
            cin >> block_tmp;
            block[block_i].push_back(block_tmp);
        }
    }
    Solution *s = new Solution();
    res = s->numberOfPatrolBlocks(block);

    cout << res << endl;

    return 0;

}