http://codeforces.com/contest/761/problem/C

题意:
给出n个串,每个串的初始光标都位于0(列)处,怎样移动光标能够在凑出密码(每个串的光标位置表示一个密码的字符,密码至少包含3种字符:数字,小写字母,特殊符号)的情况下使得移动的光标步数最小。

思路:

因为每个串只提供一个密码,所以我们先预处理计算出每个字符串3种字符的最少移动步数。

然后接下三重循环枚举,分别表示数字,小写字母,特殊符号由第i,j,k行提供。

 #include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cstdio>
using namespace std; const int inf=; int n,m;
char s[][];
int w[][]; int main()
{
//freopen("D:\\input.txt", "r", stdin);
while(~scanf("%d%d",&n,&m))
{
for(int i=;i<n;i++)
scanf("%s",&s[i]);
for(int i=;i<n;i++)
{
w[i][]=w[i][]=w[i][]=inf;
for(int j=;j<m;j++)
{
if(isdigit(s[i][j])) w[i][]=min(w[i][],min(j,m-j));
else if(islower(s[i][j])) w[i][]=min(w[i][],min(j,m-j));
else w[i][]=min(w[i][],min(j,m-j));
}
} int ans=*inf;
for(int i=;i<n;i++)
{
for(int j=;j<n;j++)
{
for(int k=;k<n;k++)
{
if(i==j||j==k||i==k) continue;
ans=min(ans,w[i][]+w[j][]+w[k][]);
}
}
}
printf("%d\n",ans);
}
return ;
}
05-11 19:48