fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. void solve(){
  5. 	int n;
  6. 	cin >> n;
  7. 	vector<string> s(2);
  8. 	for(string& x : s) cin >> x;
  9. 	vector<int> dp(4, 1e9);
  10. 	dp[3] = 0;
  11. 	// e1, e2, conn
  12. 	int last_cell = 0;
  13. 	int first_cell = -1;
  14. 	for(int i = 0; i < n; i++){
  15. 		if(s[0][i] == '*' || s[1][i] == '*'){
  16. 			last_cell = i;
  17. 			if(first_cell == -1) first_cell = i;
  18. 		}
  19. 	}
  20. 	for(int i = first_cell; i <= last_cell; i++){
  21. 		vector<int> ndp(4, 1e9);
  22. 		for(int g = 0; g < 4; g++){
  23. 			for(int a = 0; a < 4; a++){
  24. 				if((g & a) == 0) continue;
  25. 				if(!(a & 1) && s[0][i] == '*') continue;
  26. 				if(!(a & 2) && s[1][i] == '*') continue;
  27. 				ndp[a] = min(ndp[a], dp[g] + __builtin_popcount(a));
  28. 			}
  29. 		}
  30. 		dp = ndp;
  31. 	}
  32. 	int ans = 1e9;
  33. 	for(int x : dp){
  34. 		ans = min(ans, x);
  35. 	}
  36. 	cout << (ans - 1) << '\n';
  37. }
  38.  
  39. int main(){
  40. 	ios_base::sync_with_stdio(false), cin.tie(nullptr);
  41. 	int T;
  42. 	cin >> T;
  43. 	while(T--) solve();
  44. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
1
6
***.**
*.****
stdout
copy 
9
https://ideone.com/eJEMfj
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

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!