Submission #1692035

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, -1, sizeof(mat))
typedef long long ll;
const int N = 100000;
int kukan[100];

bool mizu(int x,string s){
	if(s[x]=='.')return false;
	return true;
}// 水ならtrue

int dfs(int x,int fi,string s){
	if(kukan[x] != -1) return kukan[x];
	if(x==fi)return kukan[x]=0;
	if(fi-x<4){
		if(mizu(x,s))return kukan[x]=1;
		return kukan[x]=0;
	}

	if(mizu(x,s)) {
		return kukan[x]=min(dfs(x+1,fi,s),min(dfs(x+2,fi,s),dfs(x+3,fi,s)))+1;
	}
	return kukan[x]=min(dfs(x+1,fi,s),min(dfs(x+2,fi,s),dfs(x+3,fi,s)));
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	CLR(kukan);
	int ans,n;
	string s;
	cin >> n >> s;
	ans = dfs(0,n-1,s);
	cout << ans << endl;

	
	return 0;
}

Submission Info

Judge Result