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.
這個題剛開始的時候光只是題意就坑了我很久。
題意：這個題剛開始的時候就告訴了我們正確密碼的標準格式：1.至少要有一個數字。2.至少要有一個小寫字母。3,至少要有一個特殊字符。（特殊字符指‘#’，‘&’，‘*’。）然后就是在輸入中會告訴我們n個長度為m的字符串，每個字符串都被指針會指向第一個字母。然后每次都能移動一個指針，而且只能向左或向右移動一個位置。同時這些字符串是成環狀的，例如：如果剛開始的時候指針指向第一個字符，可以向左移動一個位置指向最后一個字符。現在把每個字符串中被指的字符取出組成一個新密碼，要求新密碼符合標準格式。問最少只需移動多少次即可。
思路：首先我們要明白兩點，1.如果我們要符合標準格式就只需要用到其中的三個字符串即可。2.在每一個字符串中對于每一個條件我們需找出一個最近的即可。例如：在字符串1g1g##中對于第一個條件只需移動0步指向第一個字符即可而不用管第四個數字字符。對于第二個條件只需向右移動1步指向第二個字符g即可。對于第三個條件可以向左移動1步指向最后一個最后一個條件即可。在知道了兩點之后直接用O(n^3)的復雜度暴力一下就行了了。
#include<iostream>#include<cstring>#include<algorithm>#define MAX 55using namespace std;int n,m;int flag[MAX][5]; //用來存入每個字符串的每種字符需要多少次移動才能得到。 int min(int a,int b){ return a>b?b:a; }int Type(char c){ //函數的返回值傳入字符的種類，數字，字母，特殊字符。 	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個字符串的第type種字符的需要移動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]);				}			}		}//然后用三層循環暴力出答案。 		cout<<ans<<endl;	}}        這個思路是一個暴力代碼，雖然是O(n^3)的復雜度，但是，在這個題中的使用倒是很合理。不過我個人感覺這個題的正解應該是用dp，但是，在比賽和鏈接中貌似沒有人是使用dpAC的，大多數都是用暴力過的?？赡苁且驗閷懙姆奖愕年P系吧！不過我自己的做法是一種類似于二分圖匹配的做法。雖然最壞復雜度也是O（n^3）。但是，平均呢復雜度比較低。存儲的方式是和上面的代碼相同的方式。（如果對二分圖匹配或者深搜沒有沒有什么了解的話就跳過吧?。?/p>
#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;	} }
總結：這個題實際上光看給出的這個數據范圍本身的正解就是用來暴力的，但是，我總覺得暴力不是正解。算了......只要能AC的就是好方法。暴力出奇跡