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

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

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

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

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

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

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

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

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

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

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

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

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

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

输入

两个整数 nn 和 mm （2＜n,m≤1002＜n,m≤100）。

输出

输出 nn 行 mm 列的标记后的矩阵，输出每个数后空一格。

样例

输入

复制

3 3

输出

复制

1 2 4
3 5 7
6 8 9

#include<bits/stdc++.h>
using namespace std;
//a:存储矩阵，q:存储队列（遍历过的点） 
int a[110][110],q[10100][3];//0那列不要，从1那列开始 //探测每个点的四个方向
int fx[5]={0,0,1,0,-1};
int fy[5]={0,1,0,-1,0};
int tx,ty;//表示尝试访问的点
int k=1;//每个点标记的值，每标记一次，自增1
int n,m,i,j;
//head:头指针，指向头的位置，tail：尾指针，指向尾的位置
//有效的数据在head和tail之间。head先不动，tail往下动，当这个head里的搜完了，head再往下动
int head=1,tail=1;int main()
{cin>>n>>m;a[1][1]=k;//起点k++;//1,1点存入队列，先以1，1点为head，访问其四个方向q[1][1]=1;q[1][2]=1;while(head<=tail)//当head>tail时，说明全部搜完了{for(i=1;i<=4;i++)//周围四个方向 {//从head对应的点开始，加上方向值的变化，得到四个新点tx=q[head][1]+fx[i];ty=q[head][2]+fy[i];if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&a[tx][ty]==0){//将新点存入队列 tail++;q[tail][1]=tx;q[tail][2]=ty;a[tx][ty]=k;k++;}} head++; } for(i=1;i<=n;i++){for(j=1;j<=m;j++){cout<<a[i][j]<<" ";}cout<<endl;} return 0;} 

下面是stl的

#include<bits/stdc++.h>
using namespace std;
int a[110][110];
queue<int>q[4];
int fx[5]={0,0,1,0,-1};
int fy[5]={0,1,0,-1,0};
int tx,ty;
int k=1;
int n,m,i,j;int main()
{cin>>n>>m;a[1][1]=k;k++;q[1].push(1);q[2].push(1);while((!q[1].empty())&&(!q[2].empty())){for(i=1;i<=4;i++) {tx=q[1].front()+fx[i];ty=q[2].front()+fy[i];if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&a[tx][ty]==0){q[1].push(tx);q[2].push(ty);a[tx][ty]=k;k++;}} q[1].pop();//类似head++，head前面的不要了 q[2].pop();} for(i=1;i<=n;i++){for(j=1;j<=m;j++){cout<<a[i][j]<<" ";}cout<<endl;} return 0;}