WF2017 Secret Chamber at Mount Rushmore (邻接矩阵)

题意给出多对映射关系 (1~50)多重映射 //注意映射关系有方向,且可以间接映射
思路:就是给出每个字母对应的映射关系,我们可以想到用邻接表来存储,在连接完之后在进行一次关联(由于有些映射关系属于间接关系第一次存图没有存完整)
这里直接开邻接矩阵来存,因为所需空间不大

完整题解:

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char a[505],b[505];
int trans[30][30];
int main()
{
    int n,m;
    while(cin>>n>>m)
    {
        char x,y;
        memset(trans,0,sizeof(trans));
        
        for(int i=1; i<=n; i++)
        {
            cin>>x>>y;
            trans[x-'a'][y-'a']=1;
        }
        //间接关联
        for(int i=0; i<26; i++)
        {
            for(int j=0; j<26; j++)
            {
                if(trans[i][j]==1)
                {
                    for(int k=0; k<26; k++)
                    {
                        //所有关联i的也关联j
                        if(trans[k][i]==1)
                            trans[k][j]=1;
                    }
                }
            }
        }
        for(int p=1; p<=m; p++)
        {
            scanf("%s %s",a,b);
            int lena=strlen(a);
            int lenb=strlen(b);
            int i=0,j=0,flag=0;
            while(i<lena&&j<lenb&&i==j&&flag==0)
            {
                if(a[i]==b[j]||trans[a[i]-'a'][b[j]-'a']==1)
                {
                    i++;
                    j++;
                }
                else
                flag=1;
            }
            if(lena==lenb&&flag==0)
                cout<<"yes"<<endl;
            else//长度不等直接判no
                cout<<"no"<<endl;
        }
    }
    return 0;
}

 

上一篇:19-Halcon机器视觉实例入门:图像几何变换-仿射变换


下一篇:PAT A1010 Radix [二分]