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.
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 4
1**2
a3*0
c4**
1
5 5
#*&#*
*a1c&
&q2w*
#a3c#
*&#*&
3
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^3的暴力，复杂度O(n^3 + n*m)，代码十分好写且足以通过此题。但我们可以继续优化，不难证明，最优方案中，一定存在移动次数不超过两个，于是枚举这两个串以及移动到的什么状态即可，复杂度O(3n*n + n * m)。
思路一代码：
#include <iostream> #include <fstream> #include <sstream> #include <cstdlib> #include <cstdio> #include <cmath> #include <string> #include <cstring> #include <algorithm> #include <queue> #include <stack> #include <vector> #include <set> #include <map> #include <list> #include <iomanip> #include <cctype> #include <cassert> #include <bitset> #include <ctime> using namespace std; #define pau system("pause") #define ll long long #define pii pair<int, int> #define pb push_back #define mp make_pair #define clr(a, x) memset(a, x, sizeof(a)) const double pi = acos(-1.0); const int INF = 0x3f3f3f3f; const int MOD = 1e9 + 7; const double EPS = 1e-9; int n, m, d[55][3]; char s[55][55]; int kind(char c) { if (isalpha(c)) return 0; if (isdigit(c)) return 1; return 2; } int main() { scanf("%d%d", &n, &m); clr(d, 1); for (int i = 1; i <= n; ++i) { scanf("%s", s[i] + 1); d[i][kind(s[i][1])] = 0; for (int j = 2; j <= m; ++j) { int td = min(j - 1, m + 1 - j); int k = kind(s[i][j]); d[i][k] = min(d[i][k], td); } } int ans = INF; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { if (j == i) continue; for (int k = 1; k <= n; ++k) { if (k == i || k == j) continue; int tres = d[i][0] + d[j][1] + d[k][2]; ans = min(ans, tres); } } } printf("%d", ans); return 0; }
优化后代码：
#include <iostream> #include <fstream> #include <sstream> #include <cstdlib> #include <cstdio> #include <cmath> #include <string> #include <cstring> #include <algorithm> #include <queue> #include <stack> #include <vector> #include <set> #include <map> #include <list> #include <iomanip> #include <cctype> #include <cassert> #include <bitset> #include <ctime> using namespace std; #define pau system("pause") #define ll long long #define pii pair<int, int> #define pb push_back #define mp make_pair #define clr(a, x) memset(a, x, sizeof(a)) const double pi = acos(-1.0); const int INF = 0x3f3f3f3f; const int MOD = 1e9 + 7; const double EPS = 1e-9; int n, m, d[55][3]; char s[55][55]; int cnt[3]; int kind(char c) { if (isalpha(c)) return 0; if (isdigit(c)) return 1; return 2; } const int dir[][2] = {0, 1, 1, 2, 0, 2}; int ans = INF; void solve(int i, int j, int x, int y) { int ki = kind(s[i][1]); int kj = kind(s[j][1]); --cnt[ki], --cnt[kj]; ++cnt[x], ++cnt[y]; if (cnt[0] && cnt[1] && cnt[2]) { ans = min(ans, d[i][x] + d[j][y]); } ++cnt[ki], ++cnt[kj]; --cnt[x], --cnt[y]; } int main() { scanf("%d%d", &n, &m); clr(d, 1); for (int i = 1; i <= n; ++i) { scanf("%s", s[i] + 1); int k = kind(s[i][1]); ++cnt[k]; d[i][k] = 0; for (int j = 2; j <= m; ++j) { int td = min(j - 1, m + 1 - j); int k = kind(s[i][j]); d[i][k] = min(d[i][k], td); } } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { if (j == i) continue; for (int k = 0; k < 3; ++k) { int x = dir[k][0], y = dir[k][1]; solve(i, j, x, y); } } } printf("%d", ans); return 0; }