Advertisement
Guest User

Untitled

a guest
Aug 6th, 2013
87
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.60 KB | None | 0 0
  1. import java.util.*;
  2. import java.io.*;
  3. import java.math.*;
  4. import java.awt.geom.*;
  5.  
  6. import static java.lang.Math.*;
  7.  
  8. public class Solution implements Runnable {
  9.  
  10. public void solve() throws Exception {
  11. int n = sc.nextInt(), m = sc.nextInt();
  12. char[][] field = new char[n][];
  13. for (int i = 0; i < n; i++) {
  14. field[i] = in.readLine().toCharArray();
  15. }
  16.  
  17. int[][] ans = new int[n][m];
  18. for (int i = 0; i < n; i++) {
  19. Arrays.fill(ans[i], Integer.MAX_VALUE / 4);
  20. }
  21.  
  22. int[] last = new int[m];
  23.  
  24. Arrays.fill(last, -1);
  25. for (int i = 0; i < n; i++) {
  26. for (int j = 0; j < m; j++) {
  27. if (field[i][j] == '1') {
  28. last[j] = i;
  29. }
  30. }
  31. for (int j = 0; j < m; j++) {
  32. for (int k = 0; k < m; k++) {
  33. if (last[k] == -1) {
  34. continue;
  35. }
  36. ans[i][j] = min(ans[i][j], (j - k) * (j - k) + (i - last[k]) * (i - last[k]));
  37. }
  38. }
  39. }
  40.  
  41. Arrays.fill(last, -1);
  42. for (int i = n - 1; i >= 0; i--) {
  43. for (int j = 0; j < m; j++) {
  44. if (field[i][j] == '1') {
  45. last[j] = i;
  46. }
  47. }
  48. for (int j = 0; j < m; j++) {
  49. for (int k = 0; k < m; k++) {
  50. if (last[k] == -1) {
  51. continue;
  52. }
  53. ans[i][j] = min(ans[i][j], (j - k) * (j - k) + (i - last[k]) * (i - last[k]));
  54. }
  55. }
  56. }
  57.  
  58. for (int i = 0; i < n; i++) {
  59. for (int j = 0; j < m; j++) {
  60. out.print(ans[i][j] + " ");
  61. }
  62. out.println();
  63. }
  64. }
  65.  
  66. static Throwable uncaught;
  67.  
  68. BufferedReader in;
  69. FastScanner sc;
  70. PrintWriter out;
  71.  
  72. @Override
  73. public void run() {
  74. try {
  75. in = new BufferedReader(new InputStreamReader(System.in));
  76. out = new PrintWriter(System.out);
  77. sc = new FastScanner(in);
  78. solve();
  79. } catch (Throwable uncaught) {
  80. Solution.uncaught = uncaught;
  81. } finally {
  82. out.close();
  83. }
  84. }
  85.  
  86. public static void main(String[] args) throws Throwable {
  87. Thread thread = new Thread(null, new Solution(), "", (1 << 26));
  88. thread.start();
  89. thread.join();
  90. if (Solution.uncaught != null) {
  91. throw Solution.uncaught;
  92. }
  93. }
  94.  
  95. }
  96.  
  97. class FastScanner {
  98.  
  99. BufferedReader in;
  100. StringTokenizer st;
  101.  
  102. public FastScanner(BufferedReader in) {
  103. this.in = in;
  104. }
  105.  
  106. public String nextToken() throws Exception {
  107. while (st == null || !st.hasMoreTokens()) {
  108. st = new StringTokenizer(in.readLine());
  109. }
  110. return st.nextToken();
  111. }
  112.  
  113. public int nextInt() throws Exception {
  114. return Integer.parseInt(nextToken());
  115. }
  116.  
  117. public long nextLong() throws Exception {
  118. return Long.parseLong(nextToken());
  119. }
  120.  
  121. public double nextDouble() throws Exception {
  122. return Double.parseDouble(nextToken());
  123. }
  124.  
  125. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement