1689: 【例】【入门】快乐的马里奥(1751)
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：10
解决：7
题目描述
马里奥是一个快乐的油漆工人，这天他接到了一个油漆任务，要求马里奥把一个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列的标记后的矩阵，输出每个数后空一格。
样例输入 复制
3 3样例输出 复制
1 2 4
3 5 7
6 8 9提示
#include<bits/stdc++.h>
using namespace std;
#define N 110
struct coord {
int x,y;
};
queue<coord> Q;
int a[N][N];
int dx[5]={0,0,1,0,-1};
int dy[5]={0,1,0,-1,0};
int k=1;
int main(){
memset(a,0,sizeof(a));
int n,m;
cin>>n>>m;
coord tmp = {1,1};
Q.push(tmp);
a[1][1] = 1;
while(!Q.empty()){
coord u=Q.front();
int ux=u.x,uy=u.y;
Q.pop();
for(int i=1;i<=4;i++){
int x=ux+dx[i],y=uy+dy[i];
int d=a[ux][uy];
if (x<1||x>n||y<1||y>m||a[x][y]!=0){
continue;
}
k++;
a[x][y]=k;
coord tmp={x, y};
Q.push(tmp);
}
}
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++){
cout<<a[i][j]<<" ";
}
cout<<endl;
}
return 0;
}