FA进阶1:7-2 DFA多余状态的查找和删除
题目详情:
题目链接:https://pintia.cn/problem-sets/1632288494993354752/exam/problems/1632288744269238273
思考:按照题目所说,我们需要查找初态无法到达的状态,查找无法到达终态的状态
首先,对于输入,状态和边弧我们都看成是char类型的,存邻接表的时候会存在char类型向int类型的转换
但是这样有一个问题就是对于两位数以上的状态我们是没办法处理的,显然这道题的案例中没有这种情况
bfs1:建立好邻接表之后我们需要查找初态都无法到达的状态,
则我们需要用一个bool类型的数组来标记这个状态是不是初态可以到达的,
然后利用bfs,将初态可以到达的状态入队,出队持续更新...
bfs2:为了查找无法到达终态的状态,我们需要运用类似于上面的方法,
但由于我们需要反向遍历这个图,所以我们开了一个rh数组,
来存一个有向边的相反的情况,这样我们就可以实现反向遍历了...
具体代码如下:
#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
vector<char> not_final_state;
vector<char> initial_state;
vector<char> final_state;
vector<char> all;
const int N = 1010;
int h[N],ne[N],idx;
int rh[N];
bool st[N];//用来标记这个点能不能达到
bool st_r[N];//用来标记这个状态能不能到达终态
char e[N],w[N];
void add(char a,char b,char c)
{
e[idx]=b;
ne[idx]=h[a];
w[idx]=c;
h[a]=idx++;
}
void add_rh(char a,char b)
{
e[idx]=b;
ne[idx]=rh[a];
rh[a]=idx++;
}
void cin_init();
void bfs()
{
queue<char> q;
for(int i=0;i<initial_state.size();i++)
{
q.push(initial_state[i]);
st[initial_state[i]]=true;
}
while(q.size())
{
char t=q.front();
q.pop();
for(int i=h[t];i!=-1;i=ne[i])
{
char j=e[i];
if(!st[j])
{
q.push(j);
st[j]=true;
}
}
}
}
void bfs2()
{
queue<char> q;
for(int i=0;i<final_state.size();i++)
{
q.push(final_state[i]);
st_r[final_state[i]]=true;
}
while(q.size())
{
char t=q.front();
q.pop();
for(int i=rh[t];i!=-1;i=ne[i])
{
char j=e[i];
if(!st_r[j])
{
q.push(j);
st_r[j]=true;
}
}
}
}
int main()
{
cin_init();
bfs();//查找初态无法到达的状态
bfs2();
for(int i=0;i<all.size();i++)
{
char p=all[i];
if(!st[p]||!st_r[p])continue;//||!st_r[p]
string a;
for(int j=h[p];j!=-1;j=ne[j])
{
char k=e[j];
if(st[k]&&st_r[k])//&&st_r[k]
{
//cout<<"j="<<j<<" ne[j]="<<ne[j]<<" p="<<p<<" k="<<k<<endl;
string b;
b=b+p+" "+w[j]+" "+k+"\n";
a=b+a;
}
}
cout<<a;
}
return 0;
}
void cin_init()
{
int n;char c;
scanf("%d",&n);
//非终态
for(int i=0;i<n;i++)
{
cin>>c; not_final_state.push_back(c);
all.push_back(c);
}
getchar();
//初态
char in[100];
fgets(in,99,stdin);
for(int i=0;i<strlen(in);i++)
{if(in[i]!=' ')initial_state.push_back(in[i]);}
//终态
scanf("%d",&n);
for(int i=0;i<n;i++)
{
cin>>c;final_state.push_back(c);
all.push_back(c);
}
//状态函数
memset(h,-1,sizeof(h));
memset(rh,-1,sizeof(rh));
scanf("%d",&n);
for(int i=0;i<n;i++)
{
char a,b;
cin>>a>>b>>c;
add(a,c,b);
add_rh(c,a);
}
sort(all.begin(),all.end());
}