fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int n,m;
  5. bool chk(int i,int j){
  6. 	if(i>=0 && i<n && j>=0 && j<m){return true;}
  7. 	return false;
  8. }
  9.  
  10. int main(){
  11. 	#ifndef ONLINE_JUDGE
  12. 	freopen("input.in","r",stdin);
  13. 	freopen("output.out","w",stdout);
  14. 	#endif
  15.  
  16. 	int sx,sy;
  17. 	cin>>m>>n;
  18.  
  19. 	char arr[n][m];
  20. 	for(int i=0;i<n;i++){
  21. 		for(int j=0;j<m;j++){
  22. 			cin>>arr[i][j];
  23. 			if(arr[i][j]=='C'){sx=i;sy=j;}
  24. 		}
  25. 	}
  26.  
  27. 	int level[n][m];
  28. 	for(int i=0;i<n;i++){
  29. 		for(int j=0;j<m;j++){
  30. 			level[i][j]=INT_MAX;
  31. 		}
  32. 	}
  33.  
  34. 	queue<pair<int,pair<int,int> > > q;
  35. 	q.push(make_pair(0,make_pair(sx,sy)));
  36.  
  37. 	level[sx][sy]=0;
  38. 	while(!q.empty()){
  39. 		pair<int,pair<int,int> > p = q.front();q.pop();
  40. 		int x = p.second.first,y = p.second.second,d = p.first;
  41.  
  42. 		if(chk(x-1,y)){
  43. 			if(arr[x-1][y]=='.' || arr[x-1][y]=='C'){
  44. 				if(d==0 || d==1){
  45. 					if(level[x-1][y] > level[x][y]){
  46. 						level[x-1][y]=level[x][y];
  47. 						q.push(make_pair(1,make_pair(x-1,y)));
  48. 					}
  49. 				}else if(d==2 || d==4){
  50. 					if(level[x-1][y] > level[x][y]+1){
  51. 						level[x-1][y]=level[x][y]+1;
  52. 						q.push(make_pair(1,make_pair(x-1,y)));
  53. 					}
  54. 				}
  55. 			}
  56. 		}
  57. 		if(chk(x+1,y)){
  58. 			if(arr[x+1][y]=='.' || arr[x+1][y]=='C'){
  59. 				if(d==0 || d==3){
  60. 					if(level[x+1][y] > level[x][y]){
  61. 						level[x+1][y]=level[x][y];
  62. 						q.push(make_pair(3,make_pair(x+1,y)));
  63. 					}
  64. 				}else if(d==2 || d==4){
  65. 					if(level[x+1][y] > level[x][y]+1){
  66. 						level[x+1][y]=level[x][y]+1;
  67. 						q.push(make_pair(3,make_pair(x+1,y)));
  68. 					}
  69. 				}
  70. 			}
  71. 		}
  72. 		if(chk(x,y-1)){
  73. 			if(arr[x][y-1]=='.' || arr[x][y-1]=='C'){
  74. 				if(d==0 || d==4){
  75. 					if(level[x][y-1] > level[x][y]){
  76. 						level[x][y-1]=level[x][y];
  77. 						q.push(make_pair(4,make_pair(x,y-1)));
  78. 					}
  79. 				}else if(d==1 || d==3){
  80. 					if(level[x][y-1] > level[x][y]+1){
  81. 						level[x][y-1]=level[x][y]+1;
  82. 						q.push(make_pair(4,make_pair(x,y-1)));
  83. 					}
  84. 				}
  85. 			}
  86. 		}
  87. 		if(chk(x,y+1)){
  88. 			if(arr[x][y+1]=='.' || arr[x][y+1]=='C'){
  89. 				if(d==0 || d==2){
  90. 					if(level[x][y+1] > level[x][y]){
  91. 						level[x][y+1]=level[x][y];
  92. 						q.push(make_pair(2,make_pair(x,y+1)));
  93. 					}
  94. 				}else if(d==1 || d==3){
  95. 					if(level[x][y+1] > level[x][y]+1){
  96. 						level[x][y+1]=level[x][y]+1;
  97. 						q.push(make_pair(2,make_pair(x,y+1)));
  98. 					}
  99. 				}
  100. 			}
  101. 		}
  102. 	}
  103. 	int ans=0;
  104. 	for(int i=0;i<n;i++){
  105. 		for(int j=0;j<m;j++){
  106. 			if(arr[i][j]=='C'){ans = max(ans,level[i][j]);}
  107. 		}
  108. 	}
  109. 	cout<<ans<<endl;
  110. }
Success #stdin #stdout 0s 16064KB
comments (?)
stdin
copy 
5 4
C.... 
*...* 
C *.*. 
.....
stdout
copy 
3
https://ideone.com/1JUMyS
language:
C++ (gcc 8.3)
created:
6 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!