fork(2) download
  1. #include <cstdio>
  2.  
  3. const int N = 1 << 10, NN = N << 10;
  4. char m[N][N];
  5. int c, dep[NN], q[NN], qh, qt, r, v[NN];
  6. int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
  7. int bfs(int x, int w, int &midx){
  8. int cd, i, j, maxd = 0;
  9. dep[x] = qh = qt = 0;
  10. q[qt++] = midx = x;
  11. v[midx] = w;
  12. while(qh != qt){
  13. x = q[qh++], i = x >> 10, j = x & 1023;
  14. cd = dep[x];
  15. for(int d = 0; d < 4; ++d){
  16. int ni = i + dx[d], nj = j + dy[d];
  17. if(ni < 0 || nj < 0 || ni >= r || nj >= c) continue;
  18. if(m[ni][nj] == '.' && v[(ni << 10) + nj] != w){
  19. v[q[qt++] = midx = (ni << 10) + nj] = w;
  20. maxd = dep[midx] = cd + 1;
  21. }
  22. }
  23. }
  24. return maxd;
  25. }
  26. int max(int a, int b){ return a > b ? a : b; }
  27.  
  28. int main(void){
  29. int ans, idx, t;
  30. for(scanf("%d", &t); t-- && scanf("%d %d", &c, &r); ){
  31. ans = 0;
  32. for(int i = 0; i < r; ++i){
  33. scanf("%s", m[i]);
  34. for(int j = 0, k = i << 10; j < c; ++j) v[k + j] = 0;
  35. }
  36. for(int i = 0; i < r; ++i)
  37. for(int j = 0; j < c; ++j)
  38. if(m[i][j] == '.' && !v[(i << 10) + j]){
  39. ans = max(ans, bfs((i << 10) + j, 2, idx));
  40. ans = max(ans, bfs(idx, 1, idx));
  41. }
  42. printf("Maximum rope length is %d.\n", ans);
  43.  
  44. }
  45. return 0;
  46. }
  47.  
Success #stdin #stdout 0s 16616KB
stdin
3
3 3
###
#.#
###
7 6
#######
#.#.###
#.#.###
#.#.#.#
#.....#
####### 
5 5 
##.## 
##.## 
.....
##.## 
##.##
stdout
Maximum rope length is 0.
Maximum rope length is 8.
Maximum rope length is 4.