算法提高题目 2 密码锁（bfs最少步数）

小鱼儿 2022-06-15 05:42 384阅读 0赞

思路:

用bfs保存每种状态,每次从状态数组中取出队头元素，进行交换，得到新数组塞进状态数组中

代码：

#include<iostream>
    #include<algorithm>
    #include<string.h>
    using namespace std;
    int n,a[15],b[15];
    int step[100000]={0};
    int ss[100000][15]={0};
    int check(int c[15])
    {
    	int i;
    	for (i=0; i<n; i++)
    	{
    		if (c[i] == 2 && i+3<n)
    		{
    			if (c[i+1]==0 && c[i+2]==1 && c[i+3]==2)
    			{
    				return 1;
    			}
    			else{
    				return 0;
    			} 
    		}
    	}
    	return 0;
    }
    int pc(int c[15],int m)
    {
    	for (int i=0; i<m; i++)
    	{
    		int j;
    		for (j=0; j<n; j++)
    		{
    			if (ss[i][j] != c[j]){
    				break;
    			}
    		}
    		if (j==n){
    			return 0;
    		}
    	}
    	return 1;
    }
    
    int bfs()
    {
    	int front = 0,tail = 1;
    	int x,y,i,j,k,top=0;
    	memcpy(ss[front],a,sizeof(a));
    	while (front < tail)
    	{
    		memcpy(a,ss[front],sizeof(ss[front]));
    		if (check(a))
    		{
    			return step[front];
    		}
    		x = top-1;
    		y = top+1;
    		memcpy(b,a,sizeof(a));
    		if (x>=0&&x<n)
    		{
    			if (a[top]!=a[x])
    			{
    				b[x] = a[top];
    				b[top] = a[x];
    				if (pc(b,tail))
    				{
    					memcpy(ss[tail],b,sizeof(b));
    					step[tail] = step[front]+1;
    					if (check(b)){
    						return step[tail];
    					}
    					tail++;
    				}
    			}
    		}
    		memcpy(b,a,sizeof(a));
    		if (y>=0 && y<n)
    		{
    			if (a[top] != a[y])
    			{
    				b[y] = a[top];
    				b[top] = a[y];
    				if (pc(b,tail))
    				{
    					memcpy(ss[tail],b,sizeof(b));
    					step[tail] = step[front]+1;
    					if (check(b)){
    						return step[tail];
    					}
    					tail++;
    				}
    			}
    		}
    		top++;
    		if (top == n){
    			top = 0;
    			front++;
    		}
    	} 
    	return -1; 
    }
    int main()
    {
    	int c,v[3]={0};
    	char str[20];
    	cin>>n;
    	cin>>str;
    	for (int i=0; i<n; i++)
    	{
    		a[i] = str[i]-'0';
    		v[a[i]]++;
    	}
    	cout<<bfs();
    	return 0;
    }