第八届湘潭大学程序设计比赛 Problem C Cipher Lock

本文主要是介绍第八届湘潭大学程序设计比赛 Problem C Cipher Lock，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

  Cipher Lock 
Accepted : 33 Submit : 130
Time Limit : 2500 MS Memory Limit : 65536 KB 
 

 题目描述守护着神秘宝藏One Piece的是一把非常神秘的密码锁，这个密码锁有n排滚轮，每个滚轮有m个格子，刻着0，1两种数字。作为一把神秘的密码锁，开锁的方式却非常的简单，只要向左或向右转动滚轮使某一列的数字全是1就可以了。（向左滚动：所有的数字向左移动一位，最左边的数字移动到最右边，如001100左滚动一次变为011000，向右滚动与向左滚动操作相同，只是方向相反），作为即将成为海贼王的你，一定会选择最帅气的开锁方式———既用最少的次数来打开守护着神秘宝藏One Piece的密码锁。那么，请问最帅气的开锁次数需要转动密码锁几次呢？
输入有多组数据输入，每个数据第一行为两个整数n，m表示有n排密码锁，每个密码锁有m个格子，其中（1≤n≤100，1≤m≤104）。接下来的有n行输入，表示每排密码锁的初始状态。
输出对每组数据输出两行，第一行输出“Case # :”表示当前是几号样例（从1开始编号），第二行，如果可以开锁就输出一个整数表示最少需要移动几次，否则输出“Give Me A BOOM please”。（均不用输出“”号）
样例输入2 3
111
000
3 6
101010
000100
100000样例输出Case #1:
Give Me A BOOM please
Case #2:
3提示对第一个样例，不可能开锁。第二个样例，可以第2行向左滚动一次，第3行向右滚动2次，最少3次就可以解锁。
作者码代码的猿猿
 

思路：因为当有一列全为1时才有解，所以，枚举N列1的情况，找到每行距离i列最近的1。 

代码： 

#include<stdio.h>
char in[101][10001];
int map[101][10001];
int jdz(int a){if (a > 0) return a;return -a;
}
int main()
{int Case = 1;int n, m;while (scanf("%d%d", &n, &m) != EOF){int sign1 = 1;for (int i = 0; i < n; i++)scanf("%s", in[i]);for (int i = 0; i < n; i++){int sign2 = 0;for (int j = 0; j < m; j++){map[i][j] = in[i][j] - '0';if (1 == map[i][j])sign2 = 1;}if (0 == sign2) sign1 = 0;}printf("Case #%d:\n", Case++);if (0 == sign1)puts("Give Me A BOOM please");else{int ans = 10000000;for (int i = 0; i < m; i++){int use = 0;for (int j = 0; j < n; j++){for (int k = 0; k <= m / 2; k++){int x = (i + k) % m;      //右移int y;if (i - k>=0) y = i - k;else y = m - jdz(i - k);  //左移if (1 == map[j][x] || 1 == map[j][y]){use += k;break;}}if (use > ans)break;}if (ans > use)ans = use;}printf("%d\n", ans);}}return 0;
}

这篇关于第八届湘潭大学程序设计比赛 Problem C Cipher Lock的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！