fork download
  1.  
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. using ll=long long;
  5. #define nl '\n'
  6. #define fn ""
  7. #define F first
  8. #define S second
  9. #define rs resize
  10. #define kt size
  11. int dx[]={-1,1,0,0};
  12. int dy[]={0,0,-1,1};
  13. int n,m;
  14. vector<vector<int>> a,cnt;
  15. vector<vector<bool>> hot;
  16. int main () {
  17. ios_base::sync_with_stdio(false);
  18. cin.tie(nullptr);
  19. if (FILE *f=fopen(fn".INP","r")) {
  20. fclose(f);
  21. freopen(fn".INP","r",stdin);
  22. freopen(fn".OUT","w",stdout);
  23. }
  24. cin >> n >> m;
  25. a.resize(n+1,vector<int>(m+1));
  26. cnt.resize(n+1,vector<int>(m+1,0));
  27. hot.resize(n+1,vector<bool>(m+1,false));
  28. for (int i=1;i<=n;i++) {
  29. for (int j=1;j<=m;j++) cin >> a[i][j];
  30. }
  31. queue<pair<int,int>> q;
  32. for (int i=1;i<=n;i++) {
  33. for (int j=1;j<=m;j++) {
  34. if ((i==1 || i==n || j==1 || j==m)
  35. && a[i][j]==0 && !hot[i][j]) {
  36. hot[i][j]=true;
  37. q.push({i,j});
  38. }
  39. }
  40. }
  41. while (!q.empty()) {
  42. auto p=q.front();
  43. q.pop();
  44. for (int k=0;k<4;k++) {
  45. int x=p.F+dx[k];
  46. int y=p.S+dy[k];
  47. if (x<1 || y<1 || x>n || y>m) continue;
  48. if (a[x][y]==0 && !hot[x][y]) {
  49. hot[x][y]=true;
  50. q.push({x,y});
  51. }
  52. }
  53. }
  54. vector<pair<int,int>> cur,nxt;
  55. for (int i=1;i<=n;i++) {
  56. for (int j=1;j<=m;j++) {
  57. if (a[i][j]==0) continue;
  58. for (int k=0;k<4;k++) {
  59. int x=i+dx[k];
  60. int y=j+dy[k];
  61. if (x<1 || y<1 || x>n || y>m) continue;
  62. if (hot[x][y]) cnt[i][j]++;
  63. }
  64. if (cnt[i][j]>=2) cur.push_back({i,j});
  65. }
  66. }
  67. int ans=0;
  68. while (!cur.empty()) {
  69. ans++;
  70. for (auto p:cur) {
  71. int i=p.F,j=p.S;
  72. a[i][j]=0;
  73. hot[i][j]=true;
  74. q.push({i,j});
  75. }
  76. nxt.clear();
  77. while (!q.empty()) {
  78. auto p=q.front();
  79. q.pop();
  80. for (int k=0;k<4;k++) {
  81. int x=p.F+dx[k];
  82. int y=p.S+dy[k];
  83. if (x<1 || y<1 || x>n || y>m) continue;
  84. if (a[x][y]==0 && !hot[x][y]) {
  85. hot[x][y]=true;
  86. q.push({x,y});
  87. }
  88. else if (a[x][y]==1) {
  89. cnt[x][y]++;
  90. if (cnt[x][y]==2) nxt.push_back({x,y});
  91. }
  92. }
  93. }
  94. cur.swap(nxt);
  95. }
  96. cout << ans;
  97. return 0;
  98. }
  99.  
Success #stdin #stdout 0s 592KB
stdin
Standard input is empty
stdout
Standard output is empty