算法核心思路

恩尼格玛机的加密过程可以简化为以下步骤：

1. 明文通过接线板进行初始置换
2. 字符依次通过三个转子
3. 通过反射转子
4. 反向通过三个转子
5. 再次通过接线板（逆置换）

代码的核心思路是：

1. 解析输入数据，提取已知信息和未知的问号位置
2. 使用深度优先搜索（DFS）枚举所有可能的问号替换方案
3. 对于每个枚举的方案，模拟恩尼格玛机的加密过程，验证是否能将密文转换为已知的明文
4. 找到正确的替换方案后输出完整明文

算法复杂度分析

• 时间复杂度：最坏情况下为O(26^k)，其中k是问号的数量。题目保证k≤3，因此最多有26^3=17576种可能，枚举是可行的。
• 空间复杂度：O(1)，因为所有数组大小都是固定的，不随输入规模变化。

这种通过枚举所有可能的密钥组合来破解密码的方法，在密码学中称为"暴力破解"。由于题目限制了问号的数量，使得这种方法在本题中是可行的。 代码如下：

#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <map>
#include <vector>
#include <iostream>
#include <algorithm>
#define moo 1000000007//10^9+7
#define PI acos(-1.0)
using namespace std;
char s[10][100];//存最原始的8行字符串
int a[10][100];//存处理后的8行字符串，处理方法是对每个字符-'a'
struct question
{
    int x;
    int y;
}que[5];//存问号在的位置，第X行第Y个字符
int cou;//存问号的数量
int cheek()//检测函数，对于当前枚举的情况，如果解密正确则返回1，否则返回0
{
    int b1[100];
    int b2[100];//将明文密文取出，因为要做修改，所以避免对原数据造成影响。
    int len=strlen(s[7]);
    for(int i=0;i<len;i++)
    {
        b1[i]=a[4][a[7][i]];//将密文第一次通过简单置换板的操作顺手做了
        b2[i]=a[6][i];
    }
    int d[4][30];//存每个转子正向通过时的电路图
    int e[4][30];//存每个转子逆向通过时的电路图
    for(int i=0;i<4;i++)
    {
        for(int j=0;j<26;j++)
        {
            int t=a[i][j];
            d[i][j]=t-j;//正向通过，从j变成t，电路是+（t-j）
            e[i][t]=j-t;//逆向通过，从t变成j，电路是+（j-t）
        }
    }
    int c[4];//存的是每个转子置换板当前的转动情况。
    for(int i=0;i<4;i++)
        c[i]=a[5][i];
    for(int i=0;i<len;i++)
    {
        for(int j=0;j<=3;j++)
        {
            b1[i]+=d[j][(b1[i]+c[j]+26)%26];
            b1[i]=(b1[i]+26)%26;
        }//当前字符依次正向通过1、2、3这三个板，因为反射板工作原理与普通的没什么两样，所以也顺手正向通过
        for(int j=2;j>=0;j--)
        {
            b1[i]+=e[j][(b1[i]+c[j]+26)%26];
            b1[i]=(b1[i]+26)%26;
        }//然后再逆向通过3、2、1这三个板。
        for(int j=0;j<26;j++)//判断这个字符逆向通过简单置换板之后是不是得到明文，如果不是，则当前枚举错误
            if(b1[i]==a[4][j]&&b2[i]!=j)
                return 0;
        c[0]++;//对于每个转子做相应转动，为处理下一个字符做准备
        if(c[0]==a[5][0]+26)
        {
            c[0]=a[5][0];
            c[1]++;
            if(c[1]==a[5][1]+26)
            {
                c[1]=a[5][1];
                c[2]++;
                if(c[2]==a[5][2]+26)
                {
                    c[2]=a[5][2];
                    c[3]++;
                    if(c[3]==a[5][3]+26)
                        c[3]=a[5][3];
                }
            }
        }
    }
    return 1;
}
int dfs(int x)
{
    if(x==cou)
    {
        if(cheek()==1)
            return 1;
        return 0;
    }
    for(int i=0;i<26;i++)//枚举每一位填'a'+i的情况
    {
        a[que[x+1].x][que[x+1].y]=i;
        if(dfs(x+1)==1)
            return 1;
    }
    return 0;
}
void init()
{//预处理八行字符串，把所有点都处理成int型，方便操作，并且把'?'都提取出来
    for(int i=0;i<8;i++)
    {
        int len=strlen(s[i]);
        for(int j=0;j<len;j++)
        {
            if(s[i][j]=='?')
            {
                cou++;
                que[cou].x=i;
                que[cou].y=j;
            }
            else
                a[i][j]=s[i][j]-'a';
        }
    }
}
int main()
{
    int T;
    cin>>T;
    int dd=T;
    while(T--)
    {
        for(int i=0;i<8;i++)
            scanf("%s",s[i]);
        cou=0;
        init();
        dfs(0);
        printf("Scenario #%d:\n",dd-T);
        int len=strlen(s[6]);
        for(int i=0;i<len;i++)
            printf("%c",a[6][i]+'a');
        printf("\n\n");
    }
    return 0;
}