Openjudge 8469:特殊密码锁暴力搜索

旧城等待， 2022-06-17 12:41 131阅读 0赞

题目链接： [点击打开链接][Link 1]

http://noi.openjudge.cn/ch0406/8469

今天又看了一遍题，觉得很简单的问题，当年考试的时候脑子抽了才会做不出来，这个可以说是 熄灯问题的简化版，当我们确定了最开始的状态后，后面的状态都可以根据最开始的状态推出来，最后看看这个状态是不是符合要求就好了，当时应该是要求最小的次数这个导致我想歪了？哎，但是实现起来还是比较慢TAT。

这个题实现的时候一个坑就是，当我想办法得到string str1的翻转过来的string str2的时候，我初始化str2为空是不能赋值的，只能先赋给str2=str1,再 翻转，另外总觉得有比这个好的方法，但是我有点忘了，直接翻转。。。好吧我想起来了，直接互换值就好了，下次再这么写。。

主要的思路是，对于第一位数如果a和b不同的话，我们可以选择翻转第一位，或者第二位两种选择，对于后面的数如果a\[i\]!=b\[i\],那么我们为了保证a\[i-1\]不被改变，只好改i+1位，很好理解，当然要从头到尾做一遍，再从尾到头做一遍。。

代码如下：

// poj_search.cpp : 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    #include<string>
    #include<iostream>
    using namespace std;
    
    string str1, str2, str3, str4;
    int a[50],b[50],a1[50],len,min_num;
    
    bool check()
    {
    	for (int i = 0; i < len; i++)
    		if (a[i] != b[i]) return false;
    	return true;
    }
    int min1(int x, int y)
    {
    	return x < y ? x : y;
    }
    
    int solve(string str1, string str2)
    {
    	for (int i = 0; i < len; i++) //a1, b
    	{
    		if (str1[i] == '0') a1[i] = 0;
    		else a1[i] = 1;
    		if (str2[i] == '0')  b[i] = 0;
    		else b[i] = 1;
    	}
    
    	min_num = 1 << 20;
    
    	//第一种情况
    	int sum = 0;
    	for (int i = 0; i < len; i++)  //初始化a数组
    		a[i] = a1[i];
    	for (int i = 0; i < len; i++)  //改变第一位的情况
    	{
    		if (i == 0)  //对于i=0的情况，特殊处理，因为可以改变当前位的状态
    		{
    			if (a[i] != b[i]) {
    				sum++;
    				a[i] = !a[i];
    				a[i + 1] = !a[i + 1];
    			}
    		}
    		else  //对于i>0的情况，如果当前a[i]!=b[i],为了保证前面的正确性，只好改变i+1的状态
    		{
    			if (a[i] != b[i])
    			{
    				if ((i + 1) >= len) break;
    				else {
    					sum++;
    					a[i] = !a[i];
    					a[i + 1] = !a[i + 1];
    					if ((i + 2) < len) a[i + 2] = !a[i + 2];
    				}
    			}
    		}
    	}
    	if (check()) min_num = min1(sum, min_num);
    
    	//第二种情况,对于第一位不做改变
    	 sum = 0;
    	for (int i = 0; i < len; i++)
    		a[i] = a1[i];
    	for (int i = 0; i < len; i++)  //不改变第一位的情况
    	{
    
    		//如果当前a[i]!=b[i],为了保证前面的正确性，只好改变i+1的状态
    
    		if (a[i] != b[i])
    		{
    			if ((i + 1) >= len) break;
    			else {
    				sum++;
    				a[i] = !a[i];
    				a[i + 1] = !a[i + 1];
    				if ((i + 2) < len) a[i + 2] = !a[i + 2];
    			}
    		}
    	}
    	if (check()) min_num = min1(min_num, sum);
    
    	if (min_num == 1 << 20) return -1;
    	else return min_num;
    
    }
    
    int main()
    {
    	cin >> str1;
    	cin >> str2;
    	len = str1.length();
    	
    	int r1, r2;
    	r1 = solve(str1, str2);
    
    	//cout << len << endl;
    	str3 = str1;
    	str4 = str2;
    
    	for (int i = 0; i < len; i++)
    	{
    		str3[i] = str1[len - i - 1];
    		str4[i] = str2[len - i - 1];
    	}
    	//cout << str3 << endl << str4 << endl;
    
    	//r2 = -1;
    	r2 = solve(str3, str4);
    
    	if (r1 == -1 && r2 == -1) cout << "impossible" << endl;
    	if (r1 == -1 && r2 != -1) cout << r2 << endl;
    	if (r1 != -1 && r2 == -1) cout << r1 << endl;
    	if (r1 != -1 && r2 != -1) cout << min1(r1, r2) << endl;
    
        return 0;
    }

[Link 1]: http://http://noi.openjudge.cn/ch0406/8469