| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 948299 | ezzzay | Mutating DNA (IOI21_dna) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "dna.h"
#include<bits/stdc++.h>
#include<string>
#include<string.h>
#include<queue>
#include<map>
#include<map.h>
#define ff first
#define ss second
#define pb push_back
void init(std::string a, std::string b) {
}
int get_distance(int x, int y) {
string s=a.substr(x,y-x+1);
string t=b.substr(x,y-x+1);
map<string,int>mp;
mp[s]=1;
queue<pair<int,int>>q;
q.push({s,1});
while(!q.empty()){
string a=q.front().ff;
int w=q.front().ss;
if(a==t){
return w-1;
}
q.pop();
for(int i=0;i<a.size();i++){
for(int j=0;j<a.size();j++){
string tmp=a;
swap(tmp[i],tmp[j]);
if(mp[tmp]==0){
mp[tmp]=w+1;
q.push({tmp,w+1});
}
}
}
}
return -1;
}
