域名备案网站负责人,室内设计培训机构排名前十,室内设计师参考网站,win7记事本做网站原题链接#xff1a;173. 矩阵距离 - AcWing题库
给定一个 N行 M 列的 01矩阵 A#xff0c;A[i][j] 与 A[k][l]]之间的曼哈顿距离定义为#xff1a; dist(i,j,k,l)|i−k||j−l||
输出一个 N 行 M 列的整数矩阵 B#xff0c;其中#xff1a; B[i][j]min1≤x≤N,1≤y≤M,A…原题链接173. 矩阵距离 - AcWing题库
给定一个 N行 M 列的 01矩阵 AA[i][j] 与 A[k][l]]之间的曼哈顿距离定义为 dist(i,j,k,l)|i−k||j−l||
输出一个 N 行 M 列的整数矩阵 B其中 B[i][j]min1≤x≤N,1≤y≤M,A[x][y]1dist(i,j,x,y)
输入格式
第一行两个整数 N,M
接下来一个 N 行 M 列的 01 矩阵数字之间没有空格。
输出格式
一个 NN 行 MM 列的矩阵 B相邻两个整数之间用一个空格隔开。
数据范围
1≤N,M≤1000
输入样例
3 4
0001
0011
0110输出样例
3 2 1 0
2 1 0 0
1 0 0 1 #includeiostream
#includealgorithm
#includecstring// 定义宏方便使用pair的first和second成员
#define x first
#define y secondusing namespace std;// 定义一个pairint, int类型的别名PII
typedef pairint,int PII;// 定义常量N和MN表示网格的最大行数M表示队列的最大大小
const int N 1010, M N*N;// 定义全局变量n和m分别表示网格的行数和列数
int n, m;// 定义一个二维字符数组g用于存储网格中的字符
char g[N][N];// 定义一个队列q用于广度优先搜索
PII q[M];// 定义一个二维整数数组dist用于存储每个位置到最近的1的距离
int dist[N][N];// 定义广度优先搜索函数bfs
void bfs()
{// 初始化dist数组所有位置的距离设为-1memset(dist, -1, sizeof dist);// 定义队列的头指针hh和尾指针ttint hh 0, tt -1;// 遍历整个网格将所有值为1的位置加入队列并将它们的距离设为0for (int i 0; i n; i){for (int j 0; j m; j){if (g[i][j] 1){dist[i][j] 0;q[tt] {i, j};}}}// 定义四个方向的移动数组dx和dyint dx[4] {-1, 0, 1, 0}, dy[4] {0, 1, 0, -1};// 开始广度优先搜索while (hh tt){// 取出队列头部元素auto t q[hh];// 遍历四个方向for (int i 0; i 4; i){// 计算新位置的坐标int a t.x dx[i], b t.y dy[i];// 如果新位置超出网格范围则跳过if (a 0 || a n || b 0 || b m) continue;// 如果新位置已经访问过则跳过if (dist[a][b] ! -1) continue;// 更新新位置的距离并将其加入队列dist[a][b] dist[t.x][t.y] 1;q[tt] {a, b};}}
}// 主函数
int main()
{// 读取网格的行数和列数scanf(%d %d, n, m);// 读取网格中的字符for (int i 0; i n; i){scanf(%s, g[i]);}// 调用广度优先搜索函数bfs();// 输出每个位置到最近的1的距离for (int i 0; i n; i){for (int j 0; j m; j){printf(%d , dist[i][j]);}printf(\n);}return 0;
}
