题目大意:
求出每个点距离‘1’的最小距离。
思路:
由于刚刚学完dp 对于这个题很自然地想到了一种dp做法 :
1. 首先考虑对于任意一个位置(i, j)
,距离它最近的1的方向无非四种:
左上,右上,左下,右下(包含边界
如图,中间粉色的方框是0,周围三个绿色,和左上角的方框是1)
先考虑离(i, j)
左上角最近‘1’的距离:
dis[i][j] = min(dis[i-1][j], dis[i][j-1]) +1
其中min是为了处理‘1’与‘0’在同一行或者同一列的情况
这样就可以从左上角到右下角进行一次扫描,得出每个位置离左上角的1最近距离
2.再从其他三个方向依次扫描,得出每个(i, j) 距离四个方向的最短距离。
3.最后取这四个值中的最小值当作dis[i][j]的值。
(最后,毕竟这个题是多源bfs的模板题,还是推荐用bfs做一遍
复杂度:
一共四次扫描,每次n ^ 2, 所以复杂度为4 * n ^ 2。
AC代码如下:
#include <bits/stdc++.h>
using namespace std;
const int N = 1010, M = 1010;
int n, m;
char g[N][M];
int dis1[N][M]; //左上 -> 右下
int dis2[N][M]; //右下 -> 左上
int dis3[N][M]; //左下 -> 右上
int dis4[N][M]; //右上 -> 左下
int main(void){
scanf("%d%d", &n, &m);
memset(dis1, 0x3f, sizeof(dis1));
memset(dis2, 0x3f, sizeof(dis2));
memset(dis3, 0x3f, sizeof(dis3));
memset(dis4, 0x3f, sizeof(dis4));
for(int i = 1; i <= n; i++){
scanf("%s", g[i] + 1);
for(int j = 1; j <= m; j++){
if(g[i][j] == '1')
dis3[i][j] = dis4[i][j] = dis1[i][j] = dis2[i][j] = 0;
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(dis1[i][j]){
dis1[i][j] = min(dis1[i-1][j], dis1[i][j-1]) + 1;
}
if(dis2[n+1-i][m+1-j]){
dis2[n+1-i][m+1-j] = min(dis2[n+2-i][m+1-j], dis2[n+1-i][m+2-j])+1;
}
if(dis3[n+1-i][j]){
dis3[n+1-i][j] = min(dis3[n+2-i][j], dis3[n+1-i][j-1]) + 1;
}
if(dis4[i][m+1-j]){
dis4[i][m+1-j] = min(dis4[i-1][m+1-j], dis4[i][m+2-j]) + 1;
}
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m;j++){
int x = min(dis1[i][j], dis2[i][j]);
x = min(x, dis4[i][j]);
x = min(x, dis3[i][j]);
printf("%d ", x);
}
printf("\n");
}
}