fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define f(i, x, n) for(int i = x; i < (int)(n); ++i)
  5.  
  6. int n, m, an[1000][1000], y[1000];
  7. char mp[1000][1001];
  8. deque<pair<pair<int, int>, pair<int, int> > > q;
  9.  
  10. void up(int r){
  11. 	q.clear();
  12. 	f(j, 0, m){
  13. 		if (mp[r][j] == '1')y[j] = r;
  14. 		if (y[j] != -1){
  15. 			int g = y[j] - r;
  16. 			g *= g;
  17. 			while (!q.empty()){
  18. 				int z = j - q.back().first.second;
  19. 				if (g <= q.back().first.first + z * z) { q.pop_back(); continue; }
  20. 				int d = g - (q.back().first.first + z * z);
  21. 				z <<= 1;
  22. 				int ntr = (d + z - 1) / z;
  23. 				int nw = j + ntr;
  24. 				if (nw == j || q.back().second.first >= nw) { q.pop_back(); continue; }
  25. 				q.back().second.second = nw;
  26. 				q.push_back(make_pair(make_pair(g, j), make_pair(nw, 1e9)));
  27. 				break;
  28. 			}
  29. 			if (q.empty())q.push_back(make_pair(make_pair(g, j), make_pair(-1, 1e9)));
  30. 		}
  31. 		if (!q.empty()){
  32. 			while (q.front().second.second <= j)q.pop_front();
  33. 			int d = j - q.front().first.second;
  34. 			an[r][j] = min(an[r][j], d * d + q.front().first.first);
  35. 		}
  36. 	}
  37. }
  38.  
  39. int main() {
  40. 	scanf("%d%d", &n, &m);
  41. 	f(i, 0, n)scanf("%s", mp[i]);
  42. 	f(i, 0, n)f(j, 0, m)an[i][j] = mp[i][j] == '1' ? 0 : 1e9;
  43. 	f(i, 0, 2){
  44. 		f(i, 0, m)y[i] = -1;
  45. 		f(i, 0, n)up(i);
  46. 		f(i, 0, m)y[i] = -1;
  47. 		for (int i = n - 1; i >= 0; --i)up(i);
  48. 		f(i, 0, n)reverse(mp[i], mp[i] + m);
  49. 		f(i, 0, n)reverse(an[i], an[i] + m);
  50. 	}
  51. 	f(i, 0, n){
  52. 		printf("%d", an[i][0]);
  53. 		f(j, 1, m)printf(" %d", an[i][j]);
  54. 		printf("\n");
  55. 	}
  56. }
Success #stdin #stdout 0s 20128KB
comments (?)
stdin
copy 
3 4
1000
0000
0010
stdout
copy 
0 1 4 5
1 2 1 2
4 1 0 1
https://ideone.com/DcnV3b
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!