題干：

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

Note

In the first test it is necessary to move the pointer of the third string to one left to get the optimal answer.

In the second test one of possible algorithms will be:

• to move the pointer of the second symbol once to the right.
• to move the pointer of the third symbol twice to the right.

?

題目大意：

? ? 有 n 個(gè)字符串，每個(gè)字符串的長(zhǎng)度是m，如果認(rèn)定一個(gè)字符串是一個(gè)密碼，則必須滿(mǎn)足：

1：至少有1個(gè)數(shù)字。2：至少有一個(gè)小寫(xiě)字母。3：至少有一個(gè) #、*或&

現(xiàn)在有n個(gè)光標(biāo)，每個(gè)光標(biāo)指向這 n 個(gè)字符串。現(xiàn)在可以移動(dòng)光標(biāo)，最后使得所有光標(biāo)指向的字符能組成一個(gè)密碼。（字符串是循環(huán)的）

題目保證一定有解。

解題報(bào)告：

? ? 這題可以直接暴力啊。看了下數(shù)據(jù)范圍，o(n^3)不超，想法造一個(gè)三次方的循環(huán)暴力出來(lái)？正好題目三個(gè)條件，所以每一層循環(huán)就是一個(gè)條件不就好了？

?

AC代碼：

#include<bits/stdc++.h> #define ll long long using namespace std; const int INF = 1000000; char s[55][55]; int shu[55],zimu[55],cc[55]; int main() {int n,m;scanf("%d%d",&n,&m);for(int i = 1; i<=n; i++) {scanf("%s",s[i]+1);shu[i] = zimu[i] = cc[i] = INF;} // memset(shu,INF,sizeof shu); // memset(zimu,INF,sizeof zimu); // memset(cc,INF,sizeof cc);for(int i = 1; i<=n; i++) {for(int j = 1; j<=m; j++) {if(s[i][j] >='0' && s[i][j] <= '9') {shu[i] = min(shu[i],min(m-j+1,j-1));}} // printf("%d\n",shu[i]);}for(int i = 1; i<=n; i++) {for(int j = 1; j<=m; j++) {if(s[i][j] >='a' && s[i][j] <= 'z') {zimu[i] = min(zimu[i],min(m-j+1,j-1));}} // printf("%d\n",zimu[i]);} for(int i = 1; i<=n; i++) {for(int j = 1; j<=m; j++) {if(s[i][j] == '#' || s[i][j] == '*' || s[i][j] == '&' ) {cc[i] = min(cc[i],min(m-j+1,j-1));}} // printf("%d\n",cc[i]);} int ans = INF;for(int i = 1; i<=n; i++) {for(int j = 1; j<=n; j++) {for(int k = 1; k<=n; k++) {if(i == j || i == k || j == k) continue; // if(ans == 1) printf("%d %d %d\n",i,j,k);ans = min(ans,shu[i]+zimu[j]+cc[k]);}}}printf("%d\n",ans);return 0 ; } //3 5 //***** //1***a //**a**

總結(jié)：

? ?1WA在沒(méi)有判斷三者處在同一行的情況。

? ?2WA在INF設(shè)置的值過(guò)大了。。因?yàn)檫@里是三個(gè)值相加啊，所以可以考慮一下1<<29之類(lèi)的數(shù)。

? 題目保證一定有解的類(lèi)型，考慮一下預(yù)處理？

這題標(biāo)解貌似是記憶化搜索？（鏈接）不過(guò)其實(shí)復(fù)雜度貌似也差不多、、

#include<bits/stdc++.h> using namespace::std;const int N=55; const int INF=0x3f3f3f3f;int n, m, dp[N][2][2][2]; char s[N][N];bool isdigit(char ch) {if(ch>='0' && ch<='9')return true;return false; }bool isletter(char ch) {if(ch>='a' && ch<='z')return true;return false; }bool issymbols(char ch) {if(ch=='*' || ch == '&' || ch == '#')return true;return false; }int solve(int pos, bool digit, bool letter, bool symbols) {if(pos==n){if(digit && letter && symbols)return 0;return INF;}if(dp[pos][digit][letter][symbols] != -1)return dp[pos][digit][letter][symbols];int ans=INF;for(int j=0; j<m; j++){int cost = min(j, m-j);if(isdigit(s[pos][j]))ans = min(ans, cost+ solve(pos+1, 1, letter, symbols));else if(isletter(s[pos][j]))ans = min(ans, cost+ solve(pos+1, digit, 1, symbols));else if(issymbols(s[pos][j]))ans = min(ans, cost+ solve(pos+1, digit, letter, 1));}return dp[pos][digit][letter][symbols]=ans; }int main() {scanf("%d%d",&n,&m);for(int i=0; i<n; i++)scanf("%s",s[i]);memset(dp, -1, sizeof(dp));printf("%d\n",solve(0,0,0,0));return 0; }

?

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的【CodeForces - 761C】Dasha and Password （暴力可过，标解dp，字符串，有坑总结）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。