fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int  N = 300;
  4. const int dx[] = {-1,1,0,0};
  5. const int dy[] = {0,0,-1,1};
  6.  
  7. int r,c;
  8. char in[N][N];
  9. int num[N][N];
  10. queue<pair<int,int> >q;
  11.  
  12. inline bool check(int x, int y) {
  13. 	if (1 <= x && x <= r && 1 <= y && y <= c) return 1;
  14. 	else return 0;
  15. }
  16.  
  17. inline void pre() {
  18. 	while (!q.empty()) {
  19. 		pair<int, int> temp = q.front();
  20. 		q.pop();
  21. 		for (int i = 0; i < 4; i++) {
  22. 			int nx = temp.first + dx[i];
  23. 			int ny = temp.second + dy[i];
  24. 			if (in[nx][ny] == '0' && check(nx, ny) && num[nx][ny] == 0) {
  25. 				num[nx][ny] = num[temp.first][temp.second] + 1;
  26. 				q.push(make_pair(nx, ny));
  27. 			}
  28. 		}
  29. 	}
  30. }
  31.  
  32. int main() {
  33. 	int t, k = 0;
  34. 	scanf("%d",&t);
  35. 	while (t--) {
  36. 		++k;
  37. 		scanf("%d%d",&r,&c);
  38. 		memset(num, 0, sizeof num);
  39. 		memset(in, 0, sizeof in);
  40. 		while (!q.empty()) q.pop();
  41. 		for (int i = 1; i <= r; i++) scanf("%s",in[i]+1);
  42. 		for (int i = 1; i <= r; i++) {
  43. 			for (int j = 1; j <= c; j++) {
  44. 				if (in[i][j] == '1') {
  45. 					num[i][j] = 0;
  46. 					q.push(make_pair(i, j));
  47. 				}
  48. 			}
  49. 		}
  50. 		pre();
  51. 		int ans = INT_MAX, tot = 0;
  52. 		for (int i = 1; i <= r; i++) {
  53. 			for (int j = 1; j <= c; j++) {
  54. 				if (in[i][j] == '0') {
  55. 					tot++;
  56. 					int temp = -1;
  57. 					for (int ii = 1; ii <= r; ii++) {
  58. 						for (int jj = 1; jj <= c; jj++) {
  59. 							if (ii == i && jj == j) continue;
  60. 							if (in[ii][jj] == '0') {
  61. 								temp = max(temp, min(num[ii][jj],abs(ii-i) + abs(jj-j)));
  62. 							}
  63. 						}
  64. 					}
  65. 					//printf("%d\n", temp);
  66. 					ans = min(ans, temp);
  67. 				}
  68. 			}
  69. 		}
  70. 		if (tot == 0) ans = 0;
  71. 		printf("Case #%d: %d\n",k, ans);
  72. 	}
  73. 	return 0;
  74. }
Success #stdin #stdout 0s 15672KB
comments (?)
stdin
copy 
1
2 3
010
000
stdout
copy 
Case #1: 1
https://ideone.com/kScqdE
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

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!