ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#212142 | #3817. 写字 | huangyuhang | 0 | 1ms | 1292kb | C++11 | 924b | 2024-10-13 11:32:53 | 2024-10-13 12:26:34 |
answer
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
int n,m;
string s,t;
map<char,vector<int>>mp;
int ans;
void DFS(int p1,int res,int p2)//pos1:S,pos2:T
{
if(res>ans)
return;
if(p2==m)
{
ans=min(res,ans);
return;
}
bool flag=false;;
if(p1>0&&t[p2]==t[p1-1])
{
flag=true;
DFS(p1-1,res+1,p2+1);
}
if(p1<n-1&&t[p2]==s[p1+1])
{
flag=true;
DFS(p1+1,res+1,p2+1);
}
if(!flag)
{
for(auto p:mp[t[p2]])
{
if(p==p1)
continue;
if(p<n-1&&t[p2]==s[p+1]||p>0&&t[p2]==s[p-1])
DFS(p,res+abs(p-p1),p2);
}
}
}
int main()
{
scanf("%d %d",&n,&m);
cin>>s;
cin>>t;
for(int i=0;i<n;i++)
{
mp[s[i]].push_back(i);
}
for(int i=0;i<m;i++)
if(!mp.count(t[i]))
{
cout<<-1;
return 0;
}
ans=INT_MAX;
for(auto p:mp[t[0]])
{
DFS(p,0,1);
}
if(ans==INT_MAX)
cout<<-1;
else
cout<<ans;
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 20
Accepted
time: 0ms
memory: 1272kb
input:
1 1 v v
output:
0
result:
ok 1 number(s): "0"
Test #2:
score: -20
Wrong Answer
time: 0ms
memory: 1292kb
input:
5 5 bacbb cabcb
output:
6
result:
wrong answer 1st numbers differ - expected: '7', found: '6'
Subtask #2:
score: 0
Wrong Answer
Test #3:
score: 0
Wrong Answer
time: 1ms
memory: 1280kb
input:
26 300 ywzhvjnpdfqtukimsrbxageloc brsmsrbxbxbxbxagagagegelococololegaxagaxaxbxbrbxbrsrsmikimikikimim...
output:
-1
result:
wrong answer 1st numbers differ - expected: '299', found: '-1'
Subtask #3:
score: 0
Time Limit Exceeded
Test #6:
score: 0
Time Limit Exceeded
input:
300 300 hgbfdbgcghedefchdabhgdddahcdedebceffegfbceehceeheggffhhddbecbfdhceeedcaeeebdaddfgccggfdcachg...