제출 #1318241

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1318241		vtnoo	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	0 / 100	1098 ms	37268 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); i++)
#define R(i, j, k) for(int i = (j); i >= (k); i--)
#define ll long long
#define sz(a) ((int) a.size())
#define all(a) a.begin(), a.end()
#define vi vector<ll>
#define pb emplace_back
#define me(a, x) memset(a, x, sizeof(a))
#define fst first
#define snd second
#define ii pair<int, int>
using namespace std;
int n;
bool valid(string s){
	for(int i=1;i<n;i++){
		if(s[i]==s[i-1])return false;
	}
	return true;
}
int main(){
	ios::sync_with_stdio(false); 
	cin.tie(nullptr);
	cin>>n;
	string s;cin>>s;
	if(valid(s))cout<<0<<endl;
	queue<string>q;
	q.push(s);
	int ans=1e9;
	unordered_map<string,int>d,v;
	d[s]=0;
	v[s]=1;
	while(sz(q)){
		string u=q.front();q.pop();
		if(d[u]==n*n)continue;
		for(int i=1;i<n;i++){
			string c=u;
			swap(c[i],c[i-1]);
			if(v.count(c))continue;
			d[c]=d[u]+1;
			if(valid(c)){
				ans=min(ans,d[c]);
			}
			v[c]=1;
			q.push(c);
		}
	}
	if(ans==1e9)cout<<-1<<endl;
	else cout<<ans<<endl;
}	

• Subtask 1: 0 / 5
• Subtask 2: 0 / 55
• Subtask 3: 0 / 15
• Subtask 4: 0 / 25