fork download
copy 
  1. #include <iostream>
  2. #include <cstring>
  3.  
  4. int visited[50][50];
  5. char arr[51][51];
  6.  
  7. bool isSafe(int i, int j, int n){
  8. 	if(i>=0 && i<n && j>=0 && j<n && visited[i][j]==0 && arr[i][j]=='?'){
  9. 		//std::cout << "i " << i << " j " << j << std::endl;
  10. 		return true;
  11. 	}
  12. 	return false;
  13. }
  14.  
  15. bool dfsutil(int n, int r, int c){
  16. 	//std::cout << "dfsutil for r " << r << " c " << c << std::endl;
  17. 	int row[]={0, 0, -1, 1};
  18. 	int col[]={-1, 1, 0, 0};
  19. 	visited[r][c]=1;
  20. 	int i,j;
  21. 	bool temp=false;
  22. 	for(int k=0;k<4;k++){
  23. 		i=r+row[k];
  24. 		j=c+col[k];
  25. 		//std::cout << "k " << k << std::endl;
  26. 		if(isSafe(i, j, n)){
  27. 			temp=true;
  28. 			dfsutil(n, i, j);
  29. 		}
  30. 	}
  31. 	return temp;
  32. }
  33.  
  34. long long dfs(int n){
  35.  
  36. 	memset(visited, 0, sizeof(int)*50*50);
  37. 	int r[]={0, 0, -1, 1};
  38. 	int c[]={-1, 1, 0, 0};
  39. 	for(int i=0;i<n;i++){
  40. 		for(int j=0;j<n;j++){
  41. 			if(arr[i][j]=='G'){
  42. 				for(int k=0;k<4;k++){
  43. 					if(arr[i+r[k]][j+c[k]] == 'G' || arr[i+r[k]][j+c[k]] == '?' || arr[i+r[k]][j+c[k]] == 'P' || arr[i+r[k]][j+c[k]] == 'B')
  44. 						return 0;
  45. 				}
  46. 			}
  47. 			else if(arr[i][j]=='B'){
  48. 				for(int k=0;k<4;k++){
  49. 					if(arr[i+r[k]][j+c[k]] == 'G' || arr[i+r[k]][j+c[k]] == 'P')
  50. 						return 0;
  51. 					else if(arr[i+r[k]][j+c[k]] == '?')
  52. 						arr[i+r[k]][j+c[k]] = 'B';
  53. 				}
  54. 			}
  55. 			else if(arr[i][j]=='P'){
  56. 				for(int k=0;k<4;k++){
  57. 					if(arr[i+r[k]][j+c[k]] == 'G' || arr[i+r[k]][j+c[k]] == 'B')
  58. 						return 0;
  59. 					else if(arr[i+r[k]][j+c[k]] == '?')
  60. 						arr[i+r[k]][j+c[k]] = 'P';
  61. 				}
  62. 			}
  63. 		}
  64. 	}
  65.  
  66. 	/*for(int i=0;i<n;i++){
  67. 		for(int j=0;j<n;j++)
  68. 			std::cout << arr[i][j] << "  ";
  69. 		std::cout << std::endl;
  70. 	}*/
  71. 	long long ans=1;
  72. 	for(int i=0;i<n;i++){
  73. 		for(int j=0;j<n;j++){
  74. 			bool temp=false;
  75. 			bool ques=false;
  76. 			if(isSafe(i, j, n)){
  77. 				ques=true;
  78. 				temp=dfsutil(n, i, j);
  79. 			}
  80. 			if(temp && ques)
  81. 				ans *= 2;
  82. 			else if(!temp and ques)
  83. 				ans *= 3;
  84. 			ans %= 1000000007;
  85. 			//std::cout << "ans " << ans << std::endl;
  86. 			/*for(int i=0;i<n;i++){
  87. 				for(int j=0;j<n;j++)
  88. 					std::cout << visited[i][j] << "  ";
  89. 				std::cout << std::endl;
  90. 			}*/
  91. 		}
  92. 	}
  93. 	return ans;
  94. }
  95.  
  96. int main() {
  97. 	int t, n;
  98. 	std::cin >> t;
  99. 	while(t--){
  100. 		std::cin >> n;
  101. 		for(int i=0;i<n;i++)
  102. 			for(int j=0;j<n;j++)
  103. 				std::cin >> arr[i][j];
  104. 		/*for(int i=0;i<n;i++){
  105. 			for(int j=0;j<n;j++)
  106. 				std::cout << arr[i][j] << "  ";
  107. 			std::cout << std::endl;
  108. 		}*/
  109. 		std::cout << dfs(n) << std::endl;
  110. 	}
  111. 	return 0;
  112. }
Success #stdin #stdout 0s 16064KB
comments (?)
stdin
copy 
1
3
.?.
.?.
.B.
stdout
copy 
3
https://ideone.com/J8SPec
language:
C++ (gcc 8.3)
created:
7 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!