fork download 
  1. #include <map> 
  2. #include <cmath> 
  3. #include <ctime> 
  4. #include <deque> 
  5. #include <queue> 
  6. #include <stack> 
  7. #include <cctype> 
  8. #include <cstdio> 
  9. #include <string> 
  10. #include <vector> 
  11. #include <climits> 
  12. #include <cstdlib> 
  13. #include <cstring> 
  14. #include <fstream> 
  15. #include <iomanip> 
  16. #include <numeric> 
  17. #include <sstream> 
  18. #include <utility> 
  19. #include <iostream> 
  20. #include <algorithm> 
  21.  
  22. using namespace std;
  23.  
  24. struct dat{
  25. 	string cad;
  26. 	int prof;
  27. 	dat(string pcad, int pprof)
  28. 	{
  29. 		cad = pcad;
  30. 		prof = pprof;
  31. 	}
  32. 	dat()
  33. 	{
  34. 		cad = "";
  35. 		prof = -1;
  36. 	}
  37. };
  38.  
  39. class LightSwitchingPuzzle {
  40. public:
  41. 	map<string, bool> check;
  42. 	int checkN[1001];
  43. 	queue<dat> Q;
  44.    int minFlips( string state ) {
  45. 	   int n = state.length();
  46. 	   string s1, s2;
  47.  
  48. 	   for(int i=0;i<n;i++)
  49. 	   {
  50. 		   s1.push_back('Y');
  51. 		   s2.push_back('N');
  52. 		   checkN[i] = 0;
  53. 	   }
  54.  
  55. 	   if(state == s1)
  56. 		   return 1;
  57. 	   else if(state == s2)
  58. 		   return 0;
  59. 	   else
  60. 	   {
  61. 			dat Qfront;
  62. 			string temp;
  63. 			check[state] = 1;
  64. 			Q.push(dat(state, 0));
  65.  
  66. 			while(!Q.empty())
  67. 			{
  68. 				Qfront = Q.front();				
  69. 				Q.pop();
  70. 				bool can = true;
  71. 				for(int i=1;i<=n && can;i++)
  72. 				{
  73. 					if(checkN[i-1])
  74. 						continue;
  75.  
  76. 					if(Qfront.cad[i-1] == 'Y')
  77. 					{
  78. 						string temp = Qfront.cad;					
  79.  
  80. 						for(int j=i-1;j<n;j+=i)
  81. 						{
  82. 							temp[j] = (Qfront.cad[j] == 'Y' ? 'N' : 'Y');
  83. 						}
  84.  
  85. 						if(temp == s2)
  86. 							return Qfront.prof + 1;
  87. 						if(!check[temp])
  88. 						{
  89. 							check[temp] = 1;
  90. 							checkN[i-1] = 1;						
  91. 							Q.push(dat(temp, Qfront.prof + 1));
  92. 							can = false;
  93. 							break;
  94. 						}
  95. 					}				
  96. 				}				
  97. 			}
  98. 			return -1;
  99. 	   }
  100.    }
  101. };
  102.  
  103. int main() {
  104. 	LightSwitchingPuzzle obj;
  105. 	string cad;
  106. 	cin >> cad;
  107. 	cout << obj.minFlips(cad) << endl;
  108. 	return 0;
  109. }
Success #stdin #stdout 0s 3484KB
comments (?)
stdin 
YNN
stdout 
3
https://ideone.com/eMbJdf
language:
C++ (gcc 8.3)
created:
10 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!