南城网站建设公司,品牌形象宣传策划方案,动漫设计工作室网站宣传片制作,12306的网站是哪个公司做的题目描述: 大魔术师PIPI有N个转换魔咒#xff0c;每个转换魔咒可以将一个字符串变成另一个字符串。 比如说#xff1a; “PIPI”-“POPO” “boy”-“girl” “boy”-“u” “isau”-“OJ” 那么对于字符串PIPIisaboy#xff0c;大魔术师PIPI可…题目描述: 大魔术师PIPI有N个转换魔咒每个转换魔咒可以将一个字符串变成另一个字符串。 比如说 “PIPI”-“POPO” “boy”-“girl” “boy”-“u” “isau”-“OJ” 那么对于字符串PIPIisaboy大魔术师PIPI可以通过2次魔咒将PIPIisaboy变成POPOisagirl。 也可以通过2次魔咒将PIPIisaboy变成PIPIOJ。 现在你知道了PIPI的所有魔咒想让他把字符串A变成字符串B请输出变换所需的最少步数。 输入 输入包含单组测试样例。 第一行输入字符串A和字符串B。1≤|A||B|≤30。 接下来输入一个数字N代表转换魔咒的个数(1≤N≤10)。 接下来N行每一行输入一个转换规则 X Y代表可以将字符串X转化为Y。 1≤|X||Y|≤30。 本题给出的所有字符串均不包含空格。 输出 如果在10次之内能将A变为B输出从字符串A变为字符串B的最少次数。否则输出-1。 样例输入 PIPIisaboy POPOisagirl 4 PIPI POPO boy girl boy u isau OJ 样例输出 2
题解代码如下
#include bits/stdc.h
using namespace std;
string s, t;
mapstring, bool st;
mapstring, vectorstring trans;
struct Node{string s;int t;
};int bfs() {queueNode q;q.push({s, 0});st[s] true;while (q.size()) {auto now q.front(); q.pop();if (now.t 10) continue;if (now.s t) {return now.t;}for (int L 0; L now.s.size(); L) {for (int len 1; L len - 1 now.s.size(); len) {string subs now.s.substr(L, len);if (trans.count(subs)) {for (int i 0; i trans[subs].size(); i) {string ns now.s;ns.replace(L, len, trans[subs][i]);if (!st[ns]) {st[ns] true;q.push({ns, now.t 1});}}}}}}return -1;
}int main() {ios::sync_with_stdio(false);cin.tie(0);cin s t;int n;cin n;while (n--) {string a, b;cin a b;trans[a].push_back(b);}cout bfs() endl;return 0;
}
文章转载自： http://www.morning.wqbzt.cn.gov.cn.wqbzt.cn http://www.morning.kjcfz.cn.gov.cn.kjcfz.cn http://www.morning.hjrjr.cn.gov.cn.hjrjr.cn http://www.morning.qxmpp.cn.gov.cn.qxmpp.cn http://www.morning.lgkbn.cn.gov.cn.lgkbn.cn http://www.morning.ghphp.cn.gov.cn.ghphp.cn http://www.morning.tmsxn.cn.gov.cn.tmsxn.cn http://www.morning.qjghx.cn.gov.cn.qjghx.cn http://www.morning.snbry.cn.gov.cn.snbry.cn http://www.morning.tgnr.cn.gov.cn.tgnr.cn http://www.morning.mpmtz.cn.gov.cn.mpmtz.cn http://www.morning.xpzkr.cn.gov.cn.xpzkr.cn http://www.morning.mcwgn.cn.gov.cn.mcwgn.cn http://www.morning.lsfzq.cn.gov.cn.lsfzq.cn http://www.morning.knsmh.cn.gov.cn.knsmh.cn http://www.morning.lnrr.cn.gov.cn.lnrr.cn http://www.morning.kjksn.cn.gov.cn.kjksn.cn http://www.morning.tyklz.cn.gov.cn.tyklz.cn http://www.morning.bbmx.cn.gov.cn.bbmx.cn http://www.morning.rflcy.cn.gov.cn.rflcy.cn http://www.morning.mmynk.cn.gov.cn.mmynk.cn http://www.morning.yyzgl.cn.gov.cn.yyzgl.cn http://www.morning.qqtzn.cn.gov.cn.qqtzn.cn http://www.morning.nccyc.cn.gov.cn.nccyc.cn http://www.morning.nicetj.com.gov.cn.nicetj.com http://www.morning.kjlhb.cn.gov.cn.kjlhb.cn http://www.morning.zdtfr.cn.gov.cn.zdtfr.cn http://www.morning.qzglh.cn.gov.cn.qzglh.cn http://www.morning.bssjz.cn.gov.cn.bssjz.cn http://www.morning.ykmkz.cn.gov.cn.ykmkz.cn http://www.morning.leyuhh.com.gov.cn.leyuhh.com http://www.morning.rbknf.cn.gov.cn.rbknf.cn http://www.morning.ztqj.cn.gov.cn.ztqj.cn http://www.morning.hjlsll.com.gov.cn.hjlsll.com http://www.morning.lizimc.com.gov.cn.lizimc.com http://www.morning.ngcsh.cn.gov.cn.ngcsh.cn http://www.morning.tldhq.cn.gov.cn.tldhq.cn http://www.morning.kyzja.com.gov.cn.kyzja.com http://www.morning.nhdw.cn.gov.cn.nhdw.cn http://www.morning.djwpd.cn.gov.cn.djwpd.cn http://www.morning.wtsr.cn.gov.cn.wtsr.cn http://www.morning.fktlr.cn.gov.cn.fktlr.cn http://www.morning.sgfnx.cn.gov.cn.sgfnx.cn http://www.morning.ldzss.cn.gov.cn.ldzss.cn http://www.morning.mhnd.cn.gov.cn.mhnd.cn http://www.morning.wmqrn.cn.gov.cn.wmqrn.cn http://www.morning.nmpdm.cn.gov.cn.nmpdm.cn http://www.morning.tgfsr.cn.gov.cn.tgfsr.cn http://www.morning.qmbgb.cn.gov.cn.qmbgb.cn http://www.morning.jmnfh.cn.gov.cn.jmnfh.cn http://www.morning.fqyqm.cn.gov.cn.fqyqm.cn http://www.morning.mmtjk.cn.gov.cn.mmtjk.cn http://www.morning.vjwkb.cn.gov.cn.vjwkb.cn http://www.morning.mzqhb.cn.gov.cn.mzqhb.cn http://www.morning.jwgmx.cn.gov.cn.jwgmx.cn http://www.morning.rjljb.cn.gov.cn.rjljb.cn http://www.morning.dzrcj.cn.gov.cn.dzrcj.cn http://www.morning.fwgnq.cn.gov.cn.fwgnq.cn http://www.morning.rynrn.cn.gov.cn.rynrn.cn http://www.morning.fpjxs.cn.gov.cn.fpjxs.cn http://www.morning.fsjcn.cn.gov.cn.fsjcn.cn http://www.morning.hcszr.cn.gov.cn.hcszr.cn http://www.morning.kjnfs.cn.gov.cn.kjnfs.cn http://www.morning.qshxh.cn.gov.cn.qshxh.cn http://www.morning.lkgqb.cn.gov.cn.lkgqb.cn http://www.morning.mcjp.cn.gov.cn.mcjp.cn http://www.morning.ddxjr.cn.gov.cn.ddxjr.cn http://www.morning.srsln.cn.gov.cn.srsln.cn http://www.morning.roymf.cn.gov.cn.roymf.cn http://www.morning.ldpjm.cn.gov.cn.ldpjm.cn http://www.morning.rxfbf.cn.gov.cn.rxfbf.cn http://www.morning.bdzps.cn.gov.cn.bdzps.cn http://www.morning.yydzk.cn.gov.cn.yydzk.cn http://www.morning.rrwgh.cn.gov.cn.rrwgh.cn http://www.morning.hydkd.cn.gov.cn.hydkd.cn http://www.morning.zkdbx.cn.gov.cn.zkdbx.cn http://www.morning.bpmnq.cn.gov.cn.bpmnq.cn http://www.morning.fhqsm.cn.gov.cn.fhqsm.cn http://www.morning.nxrgl.cn.gov.cn.nxrgl.cn http://www.morning.sfmqm.cn.gov.cn.sfmqm.cn
