Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define FI(_n) for(int i = 0;i<(_n);i++)
- #define FJ(_n) for(int j = 0;j<(_n);j++)
- #define pb push_back
- #define all(c) c.begin(),c.end()
- using namespace std;
- typedef long long ll;
- const ll INF = 1e18 + 1;
- #define ndbg 1
- int n, m;
- char p[101][101];
- int ans[101][101];
- int cnt = 0;
- int func(int x, int y)
- {
- if(x < 0 || y < 0 || x >= n || y >= m || ans[x][y] != 0 || p[x][y] == 'X') return 9;
- int tox, toy, k = 0;
- tox = x + 2; toy = y + 1;
- if(tox >= 0 && toy >= 0 && tox < n && toy < m && ans[tox][toy] == 0 && p[tox][toy] != 'X') k++;
- tox = x + 1; toy = y + 2;
- if(tox >= 0 && toy >= 0 && tox < n && toy < m && ans[tox][toy] == 0 && p[tox][toy] != 'X') k++;
- tox = x - 2; toy = y + 1;
- if(tox >= 0 && toy >= 0 && tox < n && toy < m && ans[tox][toy] == 0 && p[tox][toy] != 'X') k++;
- tox = x - 1; toy = y + 2;
- if(tox >= 0 && toy >= 0 && tox < n && toy < m && ans[tox][toy] == 0 && p[tox][toy] != 'X') k++;
- tox = x + 2; toy = y - 1;
- if(tox >= 0 && toy >= 0 && tox < n && toy < m && ans[tox][toy] == 0 && p[tox][toy] != 'X') k++;
- tox = x + 1; toy = y - 2;
- if(tox >= 0 && toy >= 0 && tox < n && toy < m && ans[tox][toy] == 0 && p[tox][toy] != 'X') k++;
- tox = x - 2; toy = y - 1;
- if(tox >= 0 && toy >= 0 && tox < n && toy < m && ans[tox][toy] == 0 && p[tox][toy] != 'X') k++;
- tox = x - 1; toy = y - 2;
- if(tox >= 0 && toy >= 0 && tox < n && toy < m && ans[tox][toy] == 0 && p[tox][toy] != 'X') k++;
- return k;
- }
- void dfs(int x, int y)
- {
- if(x < 0 || x >= n || y < 0 || y >= m) return;
- if(ans[x][y] != 0) return;
- if(p[x][y] == 'X') return;
- cnt++;
- ans[x][y] = cnt;
- vector< pair<int,pair<int,int> > > s;
- s.pb({func(x + 2, y - 1),{x + 2, y - 1}});
- s.pb({func(x + 1, y - 2),{x + 1, y - 2}});
- s.pb({func(x + 2, y + 1),{x + 2, y + 1}});
- s.pb({func(x + 1, y + 2),{x + 1, y + 2}});
- s.pb({func(x - 2, y - 1),{x - 2, y - 1}});
- s.pb({func(x - 1, y - 2),{x - 1, y - 2}});
- s.pb({func(x - 2, y + 1),{x - 2, y + 1}});
- s.pb({func(x - 1, y + 2),{x - 1, y + 2}});
- random_shuffle(all(s));
- sort(all(s));
- dfs(s[0].second.first, s[0].second.second);
- }
- int main()
- {
- ios_base::sync_with_stdio(0);
- #ifdef ndbg
- ifstream cin("input.txt");
- ofstream cout("output.txt");
- #endif
- cin.tie(0);cout.tie(0);
- cin >> n >> m;
- int sx, sy;
- FI(n)
- FJ(m)
- {
- cin>>p[i][j];
- if(p[i][j] == 'K') sx = i, sy = j;
- }
- dfs(sx, sy);
- FI(n)
- {
- FJ(m) cout << ans[i][j]<<" ";
- cout<<"\n";
- }
- #ifdef ndbg
- cin.close();
- cout.close();
- #endif
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement