【入门】快乐的马里奥 c++

Question

说明
马里奥是一个快乐的油漆工人，这天他接到了一个油漆任务，要求马里奥把一个n行m列的矩阵每一格都用油漆标记一个数字，标记的顺序按照广度优先搜索的方式进行，也就是他会按照如下方式标记：

1、首先标记第1行第1列的单元格，标记数字为1；

2、然后标记当前单元格上下左右四个方向所有能标记的单元格，且：

① 标记顺序按照：右、下、左、上的优先级；

② 不能标记到矩阵外，且标记过的数字不能重复标记；

3、当本单元格标记结束，寻找比本单元格中数字大1的单元格，标记那个单元格的上下左右四个方向，也是按照步骤2所示的要求进行标记。

依次类推，直到所有单元格都被标记。

比如：如果有一个3 * 3的矩阵如下，那么首先标记1,1单元格，并按照上面步骤2的要求标记其四周能够标记的单元格，标记结果如下：

接下来，标记比1,1格大1的数字的四周的单元格，也就是标记值为2的单元格四周的单元格，标记结果如下：

接下来标记值为3的单元格四周的单元格，标记结果如下：

接下来标记值为4的单元格四周的单元格，标记结果如下：

接下来标记值为5的单元格四周的单元格，标记结果如下：

接下来标记值为6的单元格四周的单元格，但这个数字四周的单元格已经被标记，因此继续标记值为7四周的单元格，标记结果如下：

此时，发现标记结束，得到如上图所示的标记结果。

输入格式
两个整数n和m，n和m都是3~100之间的整数。

输出格式
输出n行m列的标记后的矩阵，输出每个数后空一格。

样例
输入数据 1
3 3
输出数据 1
1 2 4
3 5 7
6 8 9

Answer 1

int main()
{
    int n, m;
    cin >> n >> m;
    int s = n * m;
    int i = 1;
    deque<pair<int,int>> dq;
    dq.push_back(make_pair(0,0));
    vector<vector<int>> matrix(n, vector<int>(m));
    matrix[0][0] = i;
    i++;
    while (!dq.empty()&&i<=s) {
        auto pos = dq.front();
        dq.pop_front();
        int r = pos.first;
        int c = pos.second;
        //右
        int rr = r;
        int cr = c + 1;
        if (cr < m  && matrix[rr][cr] == 0) {
            matrix[rr][cr] = i;
            i++;
            dq.push_back(make_pair(rr, cr));
        }
        //下
        int rd = r + 1;
        int cd = c;
        if (rd < n  && matrix[rd][cd] == 0) {
            matrix[rd][cd] = i;
            i++;
            dq.push_back(make_pair(rd, cd));
        }
        //左
        int rl = r;
        int cl = c - 1;
        if (cl >= 0 && matrix[rl][cl] == 0) {
            matrix[rl][cl] = i;
            i++;
            dq.push_back(make_pair(rl, cl));
        }              
        //上
        int ru = r - 1;
        int cu = c;
        if (ru >= 0 && matrix[ru][cu] == 0) {
            matrix[ru][cu] = i;
            i++;
            dq.push_back(make_pair(ru, cu));
        }
    }           
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout << matrix[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}