C. Dasha and Password

C. Dasha and Password time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output

After overcoming the stairs Dasha came to classes. She needed to write a password to begin her classes. The password is a string of length n which satisfies the following requirements:

• There is at least one digit in the string,
• There is at least one lowercase (small) letter of the Latin alphabet in the string,
• There is at least one of three listed symbols in the string: '#', '*', '&'.

Considering that these are programming classes it is not easy to write the password.

For each character of the password we have a fixed string of length m, on each of these n strings there is a pointer on some character. The i-th character displayed on the screen is the pointed character in the i-th string. Initially, all pointers are on characters with indexes 1 in the corresponding strings (all positions are numbered starting from one).

During one operation Dasha can move a pointer in one string one character to the left or to the right. Strings are cyclic, it means that when we move the pointer which is on the character with index 1 to the left, it moves to the character with the index m, and when we move it to the right from the position m it moves to the position 1.

You need to determine the minimum number of operations necessary to make the string displayed on the screen a valid password.

Input

The first line contains two integers n, m (3 ≤ n ≤ 50, 1 ≤ m ≤ 50) — the length of the password and the length of strings which are assigned to password symbols.

Each of the next n lines contains the string which is assigned to the i-th symbol of the password string. Its length is m, it consists of digits, lowercase English letters, and characters '#', '*' or '&'.

You have such input data that you can always get a valid password.

Output

Print one integer — the minimum number of operations which is necessary to make the string, which is displayed on the screen, a valid password.

Examples input

3 4
1**2
a3*0
c4**
      

output

1
      

input

5 5
#*&#*
*a1c&
&q2w*
#a3c#
*&#*&
      

output

3      

題意就是n個串，每個串的初始光标都位于0（列）處，問你怎樣移動光标能夠在湊出密碼（每個串的光标位置表示一個密碼的字元，密碼至少包含3種字元：數字，小寫字母，特殊符号）的情況下使得移動的光标步數最小。

思路：首先考慮到的便是深搜，不過50的階乘的複雜度是撐不住的，我們要簡化一下。

 首先就是要這樣考慮，對于一個字元串，我們要的其實就是一個屬性，這個屬性指的就是那3種字元裡面的一種。可以想一下，如果前面的串已經湊齊了3種字元了，那麼後面的串就完全沒有必要去湊了，就是0。

是以說，其實對于每一個串，我們隻需要記錄3種狀态的最小值就可以了。因為後面更大的狀态完全沒有必要。我們隻是要求一個串到達某個屬性就可以了。

這樣複雜度就可以降到了50*49*48的情況。

之後看一下代碼就懂啦。

#include <bits/stdc++.h>
using namespace std;
const int MAXN=55;
const int inf =0x3f3f3f3f;
int n,m;
int w[MAXN][10];
char s[MAXN];
int ans;
bool vis[MAXN];
void dfs(int j,int sum)
{
    if(j==3)
    {
        ans=min(ans,sum);
        return;
    }
    if(sum>ans)return;

    for(int i=0;i<n;++i)
    {
        if(!vis[i])
        {
            vis[i]=1;
            dfs(j+1,sum+w[i][j]);
            vis[i]=0;
        }
    }
}

int main()
{
    int i,j;
    scanf("%d%d",&n,&m);
    memset(w,inf,sizeof(w));
    for(i=0;i<n;++i)
    {
        scanf("%s",s);
        for(j=0;j<m;++j)
        {
            if(isdigit(s[j]))w[i][0]=min(w[i][0],min(j,m-j));
            else if(islower(s[j]))w[i][1]=min(w[i][1],min(j,m-j));
            else w[i][2]=min(w[i][2],min(j,m-j));
        }
    }
    ans=inf;
    dfs(0,0);
    printf("%d\n",ans);
    return 0;
}