Div.2 C. Dasha and Password
2 seconds
256 megabytes
standard input
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 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 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...
代码:
#include "cstdio" #include "algorithm" #include "cstring" #include "queue" #include "cmath" using namespace std; ; #define inf 0x3f3f ][]; ][];// int main(){ int n,m; scanf("%d%d",&n,&m); ;i<;i++){ ;j<;j++){ d[i][j]=; } } ;i<n;i++){ scanf("%s",s[i]); } // memset(d,inf, sizeof(d)); 用inf初始化会溢出导致结果❌卡了好一会 ;i<n;i++){ ;j<=m/;j++){ '){ d[i][]=min(d[i][],j); } if(s[i][j]>='a'&&s[i][j]<='z'){ d[i][]=min(d[i][],j); } if(s[i][j]=='#'||s[i][j]=='*'||s[i][j]=='&'){ d[i][]=min(d[i][],j); } ){ ;k<=m/;k++){ '){ d[i][]=min(d[i][],k); } else if(s[i][m-k]>='a'&&s[i][m-k]<='z'){ d[i][]=min(d[i][],k); } ]=min(d[i][],k);} } } } } int a,b,c,x=inf; ;i<n;i++){ ;j<n;j++){ ;k<n;k++){ a=min(d[i][]+d[j][]+d[k][],d[i][]+d[k][]+d[j][]); b=min(d[k][]+d[i][]+d[j][],d[k][]+d[j][]+d[i][]); c=min(d[j][]+d[k][]+d[i][],d[j][]+d[i][]+d[k][]); x=min(x,min(min(a,b),c)); } } } printf("%d\n",x); ; }
最新文章
- touches
- Cheatsheet: 2016 08.01 ~ 08.31
- IIS中发布网站的问题
- 安装python爬虫scrapy踩过的那些坑和编程外的思考
- 宠物AI(个人觉得有问题)
- 深入学习 DUBBO
- JS事件及其兼容用法
- [SDOI2014]重建
- RHEL 6 mdadm 实现Soft Raid
- windows上安装zip版mongodb
- Java的内部类真的那么难以理解?
- BootStrap顺序验证和指定字符个数发送请求
- freeswitch 事件命令
- Maven pom详解
- ueditor的用法
- 学习笔记CB008:词义消歧、有监督、无监督、语义角色标注、信息检索、TF-IDF、隐含语义索引模型
- visio画图有感
- javascript:window.location.replace 与 window.location.reload() 刷新页面的不同效果
- HDU 4757 Tree 可持久化字典树 trie
- SQLSERVER误删Windows登录用户验证方式使用Windows身份验证的解决方法