UVALive - 7263 Today Is a Rainy Day(bfs)
2024-09-01 15:45:23
题意
给两个等长的只含数字1,2,3,4,5,6的字符串s(|s|≤110),有两种操作:
- 把一个位置的数字换成另一个数字,换成的数字也只能是1到6
- 把这个字符串中相同的数字都换成另一种数字
应用上面的两种操作把第二个字符串转换成第一个字符串至少需要多少次操作?
分析
首先尽可能多的进行第二次操作一定是最优的。
对于第二种操作,我们可以预处理出来变换到每个状态的最短步数,也就是用bfs跑。以123456标记为初始状态state,然后每次选择一个要变换的数字以及变换成的数字。
那么,如何求解从第二个字符串变到第一个字符串的最少步数呢?根据上面的状态定义,初始状态为123456(位置1对应数字1,位置2对应数字2....),那么每到一个新的状态nxt,先用数组存起来对应位置的change[],遍历s2,如果change[s2[j]]!=s1[j](change[s2[j]]表示s2[j]在nxt状态下变成了change[s2[j]]),则需要进行操作1,tmp++。
那么遍历所有状态,ans=min(ans,tmp+step[nxt])。
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <queue>
using namespace std;
const int MAX_N = ;
int total = , step[MAX_N], res[MAX_N], pw10[];
queue<int> que;
char s1[], s2[];
void bfs() {
pw10[] = ;
for (int i = ; i <= ; ++i) { pw10[i] = * pw10[i - ]; }
memset(step, -, sizeof (step));
int st = ;
step[st] = total, res[total++] = st;
que.push(st);
while (!que.empty()) {
int cur = que.front();
que.pop();
for (int i = ; i <= ; ++i) {
for (int j = ; j <= ; ++j) {
if (i == j) continue;
int nxt = ;
for (int k = ; k >= ; --k) {
int p = cur / pw10[k] % ;
if (p == i) nxt = nxt * + j;
else nxt = nxt * + p;
}
if (step[nxt] != -) continue;
step[nxt] = step[cur] + ;
res[total++] = nxt;
que.push(nxt);
}
}
}
}
int main() {
bfs();
while (~scanf("%s%s", s1, s2)) {
int len = strlen(s1);
int ans = len, change[];
for (int i = ; i < total; ++i) {
int cur = res[i], tmp = ;
for (int j = , k = ; j >= ; --j) {
change[k++] = cur / pw10[j] % ;
}
for (int j = ; j < len; ++j) {
int to = change[s2[j] - ''];
if (to != s1[j] - '') tmp++;
}
ans = min(ans, tmp + step[cur]);
}
printf("%d\n", ans);
}
return ;
}
最新文章
- insertAdjacentHTML方法示例
- windows 下配置 nginx的问题
- Struts2开发环境搭建,及一个简单登录功能实例
- 【过程改进】 windows下jenkins常见问题填坑
- JVM调优总结10-调优方法
- android手机操作SD的使用方法
- 项目图片上传存储的目录部分代码思路Calendar类获取年月日
- c++中basic_istream::getline()的返回值何时为真
- javascript设计模式——迭代器模式
- Trie树(字典树)推荐文章
- jQuery中哪几种选择器
- mysql 创建备份表
- Gevent 性能和 gevent.loop 的运用和带来的思考
- hdoj1905 Pseudoprime numbers (基础数论)
- Linux下的rename命令
- 显示器如何显示一个YUV422格式的图形
- Linux SSH无密码登录
- Sass进阶之路,之二(进阶篇)
- Linux主流发行版本
- Hibernate 中一级缓存和快照区的理解
热门文章
- 解决AJAX应用,会话超时(Session Timeout)的问题,粗略方法(不考虑使用Filter的前提下)
- Windows Server 2008 双网卡 断网问题 总结
- [转帖]Linux内核为大规模支持100Gb/s网卡准备好了吗?并没有
- Java多线程之原子性 volatile、atomicInteger测试
- 今天看到了一篇文档 app 测试内容记录下来
- spring boot 系列之五:spring boot 通过devtools进行热部署
- pipreqs 组件
- centos Install Mrtg
- Spring Security和 JWT两大利器来打造一个简易的权限系统。
- OpenAI 开源机器人模拟 Python 库,并行模拟处理速度提升400%