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:

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 1in 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.

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.

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

3 41**2a3*0c4**output
1input
5 5#*&#**a1c&&q2w*#a3c#*&#*&output
3Note
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.
這個(gè)題剛開始的時(shí)候光只是題意就坑了我很久。
題意：這個(gè)題剛開始的時(shí)候就告訴了我們正確密碼的標(biāo)準(zhǔn)格式：1.至少要有一個(gè)數(shù)字。2.至少要有一個(gè)小寫字母。3,至少要有一個(gè)特殊字符。（特殊字符指‘#’，‘&’，‘*’。）然后就是在輸入中會(huì)告訴我們n個(gè)長度為m的字符串，每個(gè)字符串都被指針會(huì)指向第一個(gè)字母。然后每次都能移動(dòng)一個(gè)指針，而且只能向左或向右移動(dòng)一個(gè)位置。同時(shí)這些字符串是成環(huán)狀的，例如：如果剛開始的時(shí)候指針指向第一個(gè)字符，可以向左移動(dòng)一個(gè)位置指向最后一個(gè)字符。現(xiàn)在把每個(gè)字符串中被指的字符取出組成一個(gè)新密碼，要求新密碼符合標(biāo)準(zhǔn)格式。問最少只需移動(dòng)多少次即可。
思路：首先我們要明白兩點(diǎn)，1.如果我們要符合標(biāo)準(zhǔn)格式就只需要用到其中的三個(gè)字符串即可。2.在每一個(gè)字符串中對(duì)于每一個(gè)條件我們需找出一個(gè)最近的即可。例如：在字符串1g1g##中對(duì)于第一個(gè)條件只需移動(dòng)0步指向第一個(gè)字符即可而不用管第四個(gè)數(shù)字字符。對(duì)于第二個(gè)條件只需向右移動(dòng)1步指向第二個(gè)字符g即可。對(duì)于第三個(gè)條件可以向左移動(dòng)1步指向最后一個(gè)最后一個(gè)條件即可。在知道了兩點(diǎn)之后直接用O(n^3)的復(fù)雜度暴力一下就行了了。
#include<iostream>#include<cstring>#include<algorithm>#define MAX 55using namespace std;int n,m;int flag[MAX][5]; //用來存入每個(gè)字符串的每種字符需要多少次移動(dòng)才能得到。 int min(int a,int b){ return a>b?b:a; }int Type(char c){ //函數(shù)的返回值傳入字符的種類，數(shù)字，字母，特殊字符。 	if(c>='0'&&c<='9')		return 1;	if(c>='a'&&c<='z')		return 2;	return 3;}int main(){	while(cin>>n>>m){		for(int i=0;i<n;i++){			char str[MAX];			cin>>str;			flag[i][1]=55,flag[i][2]=55,flag[i][3]=55;			for(int j=0;j<m;j++){				int type=Type(str[j]);				flag[i][type]=min(flag[i][type],min(j,m-j));//這句表示第i個(gè)字符串的第type種字符的需要移動(dòng)flag[i][type]次才能得到 			}		}		int ans=55*3;		for(int i=0;i<n;i++){			for(int j=0;j<n;j++){				for(int k=0;k<n;k++){					if(i==j||j==k||k==i)						continue;					ans=min(ans,flag[i][1]+flag[j][2]+flag[k][3]);				}			}		}//然后用三層循環(huán)暴力出答案。 		cout<<ans<<endl;	}}        這個(gè)思路是一個(gè)暴力代碼，雖然是O(n^3)的復(fù)雜度，但是，在這個(gè)題中的使用倒是很合理。不過我個(gè)人感覺這個(gè)題的正解應(yīng)該是用dp，但是，在比賽和鏈接中貌似沒有人是使用dpAC的，大多數(shù)都是用暴力過的。可能是因?yàn)閷懙姆奖愕年P(guān)系吧！不過我自己的做法是一種類似于二分圖匹配的做法。雖然最壞復(fù)雜度也是O（n^3）。但是，平均呢復(fù)雜度比較低。存儲(chǔ)的方式是和上面的代碼相同的方式。（如果對(duì)二分圖匹配或者深搜沒有沒有什么了解的話就跳過吧！）
#include<iostream>#include<cstring>#include<algorithm>#define MAX 55using namespace std;int n,m;int flag[MAX][5];int ans_flag[MAX],ans_type[4];bool vis_type[4];int min(int a,int b){ return a>b?b:a; }int abs(int a){ return a>0?a:-a; }int Type(char c){	if(c>='0'&&c<='9')		return 1;	if(c>='a'&&c<='z')		return 2;	return 3;}void dfs(int a){	for(int j=1;j<=3;j++){		if(flag[a][j]!=55&&(ans_type[j]==-1||flag[ans_type[j]][j]>flag[a][j])&&!vis_type[j]){			vis_type[j]=true;			if(ans_type[j]==-1){				ans_type[j]=a;				return;			}else{				ans_type[j]=a;				dfs(ans_type[j]);				return;			}		}	}	return;}int graph_math(){	memset(ans_type,-1,sizeof(ans_type));	int res=0;	for(int j=0;j<n;j++){		memset(vis_type,false,sizeof(vis_type));		dfs(j);	}	return flag[ans_type[1]][1]+flag[ans_type[2]][2]+flag[ans_type[3]][3];}int main(){	while(cin>>n>>m){		for(int i=0;i<n;i++){			char str[MAX];			cin>>str;			flag[i][1]=55,flag[i][2]=55,flag[i][3]=55;			for(int j=0;j<m;j++){				int type=Type(str[j]);				flag[i][type]=min(flag[i][type],min(j,m-j));			}		}		cout<<graph_math()<<endl;	} }
總結(jié)：這個(gè)題實(shí)際上光看給出的這個(gè)數(shù)據(jù)范圍本身的正解就是用來暴力的，但是，我總覺得暴力不是正解。算了......只要能AC的就是好方法。暴力出奇跡