Guest User

Untitled

a guest
Jan 11th, 2016
2,025
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. #define forn(i, n) for (int i = 0; i < int(n); i++)
  4. #define ford(i, n) for (int i = int(n) - 1; i >= 0; i--)
  5. #define fore(i, l, r) for (int i = int(l); i < int(r); i++)
  6. #define correct(x, y, n, m) (0 <= (x) && (x) < (n) && 0 <= (y) && (y) < (m))
  7. #define all(a) (a).begin(), (a).end()
  8. #define sz(a) int((a).size())
  9. #define pb(a) push_back(a)
  10. #define mp(x, y) make_pair((x), (y))
  11. #define x first
  12. #define y second
  13.  
  14. using namespace std;
  15.  
  16. typedef long long li;
  17. typedef long double ld;
  18. typedef pair<int, int> pt;
  19.  
  20. template<typename X> inline X abs(const X& a) { return a < 0? -a: a; }
  21. template<typename X> inline X sqr(const X& a) { return a * a; }
  22.  
  23. const int INF = int(1e9);
  24. const li INF64 = li(1e18);
  25. const ld EPS = 1e-9, PI = 3.1415926535897932384626433832795;
  26.  
  27. const int N = 1010;
  28.  
  29. int n, m;
  30. char a[N][N];
  31.  
  32. inline bool read() {
  33.     if (!(cin >> n >> m)) return false;
  34.     forn(i, n) assert(scanf("%s", a[i]) == 1);
  35.     return true;
  36. }
  37.  
  38. int sz[N * N];
  39. int tt, num[N][N];
  40.  
  41. int dx[] = { -1, 0, 1, 0 };
  42. int dy[] = { 0, -1, 0, 1 };
  43.  
  44. void dfs(int x, int y) {
  45.     sz[tt]++;
  46.     num[x][y] = tt;
  47.  
  48.     forn(i, 4) {
  49.         int xx = x + dx[i];
  50.         int yy = y + dy[i];
  51.         if (min(xx, yy) < 0 || xx >= n || yy >= m) continue;
  52.         if (num[xx][yy] != -1 || a[xx][yy] != '.') continue;
  53.         dfs(xx, yy);
  54.     }
  55. }
  56.  
  57. char ans[N][N];
  58.  
  59. inline void solve() {
  60.     tt = 0;
  61.     forn(i, n) forn(j, m) num[i][j] = -1;
  62.  
  63.     forn(i, n)
  64.         forn(j, m)
  65.             if (num[i][j] == -1 && a[i][j] == '.') {
  66.                 sz[tt] = 0;
  67.                 dfs(i, j);
  68.                 tt++;
  69.             }
  70.  
  71. #ifdef SU1
  72.     forn(i, n) {
  73.         forn(j, m) cerr << num[i][j] << ' ';
  74.         cerr << endl;
  75.     }
  76. #endif
  77.  
  78.     forn(i, n)
  79.         forn(j, m) {
  80.             if (a[i][j] == '.') {
  81.                 ans[i][j] = '.';
  82.                 continue;
  83.             }
  84.             int cur[4] = { -1, -1, -1, -1 };
  85.             forn(k, 4) {
  86.                 int x = i + dx[k];
  87.                 int y = j + dy[k];
  88.                 if (min(x, y) < 0 || x >= n || y >= m) continue;
  89.                 if (a[x][y] != '.') continue;
  90.                 cur[k] = num[x][y];
  91.             }
  92.             sort(cur, cur + 4);
  93.             int szcur = int(unique(cur, cur + 4) - cur);
  94.             int ans = 1;
  95.             forn(k, szcur)
  96.                 if (cur[k] != -1)
  97.                     ans += sz[cur[k]];
  98.             ans %= 10;
  99.             ::ans[i][j] = char('0' + ans);
  100.         }
  101.  
  102.     forn(i, n) puts(ans[i]);
  103. }
  104.  
  105. int main() {
  106. #ifdef SU1
  107.     assert(freopen("input.txt", "rt", stdin));
  108.     //assert(freopen("output.txt", "wt", stdout));
  109. #endif
  110.    
  111.     cout << setprecision(10) << fixed;
  112.     cerr << setprecision(5) << fixed;
  113.  
  114.     while (read()) {
  115.         solve();
  116.         //break;
  117.     }
  118.    
  119.     return 0;
  120. }
RAW Paste Data