《程序设计语⾔综合设计》第六周上机练习
3 括号匹配调整
如果通过插⼊“ +”和“ 1”可以从中得到格式正确的数学表达式，则将带括号的序列称为正确的。
例如，序列 "(())()"，"()"和 "(()(()))"是正确的，⽽")("，"(()))("和"(()" 不是。
定义重新排序操作：选择括号序列的任意连续⼦段（⼦字符串），然后以任意⽅式对其中的所有字符进⾏重新排序。当重新排序的⼦
段的长度为t时，重新排序操作需要耗时t秒。
例如，对于“))((”，他可以选择⼦字符串“)(”并重新排序“)()(”（此操作将花费2秒）。
不难看出，重新排序操作不会改变左括号和右括号的数量。
现在，LD想花费最少的时间，通过任意次数（可能为零）执⾏重新排序操作来使括号序列变成正确的。
输⼊格式:
第⼀⾏包含⼀个整数n（1≤n≤1e6），表⽰序列的长度；
第⼆⾏包含⼀个长度为n的字符串，仅由字符‘(’和‘)’组成。
输出格式:
输出⼀个整数，表⽰使括号序列正确的最⼩秒数；如果不可能实现，则输出-1。
输⼊样例:
8
))((())(
输出样例:
6
Accepted
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <stack>
using namespace std;
stack<char>s;
/*⾸先对于括号的问题很容易想到栈，那么我们对于每个左括号采取的决策是栈顶的左括号能够匹配就⽴即匹配。因为如果栈顶的括号不匹配，其他的括号也就没办法匹配。栈顶括号匹配的越晚，已经构造的⼦序列就越长。根据题意可知int main(){
int i;
int n;
char ch[1000005];
int ans=0;
cin >> n ;
// getchar();
cin >>ch;
// cout << ch;
for(i=0;i<n;i++){
if(!s.empty()&&ch[i]==')'&&p()=='('){
s.pop();
}
else if(!s.empty()&&ch[i]=='('&&p()==')'){
ans+=2;
s.pop();
}
else s.push(ch[i]);
}
if(!s.empty()) cout <<"-1"<<endl;
else cout << ans << endl;
return 0;
}
但是我发现，如果我将if和else if条件中!s.empty()放在&&后⾯就会出现段错误，这是为什么呢？
这是因为且（`&&``）的条件判断是前⼀个条件成⽴再判断后⼀个条件，如果栈为空，那么后⼀个条件判断放前⾯就⽆法进⾏。
4 奇怪的电梯
c⼤楼有⼀个⼀种很奇怪的电梯。⼤楼的每⼀层楼都可以停电梯，⽽且第 i 层楼 (1≤i≤N) 上有⼀个数字Ki(0≤Ki≤N)。电梯只有四个按
钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满⾜要求，相应的按钮就会失灵。例如：3,3,1,2,5 代
表了Ki (K1=3,K2=3,…)，在1楼，按“上”可以到4楼，按“下”是不起作⽤的，因为没有−2楼。那么，从A楼到B楼⾄少要按⼏次按钮呢？
输⼊格式:
第⼀⾏包含3个⽤空格隔开的正整数，分别表⽰N,A,B (1≤N≤200,1≤A,B≤N) 。第⼆⾏包含N 个⽤空格隔开的⾮负整数，表⽰Ki 。
输出格式:
输出共⼀⾏，即最少按键次数，若⽆法到达，则输出 −1 。
输⼊样例:
5 1 5
3 3 1 2 5
输出样例:
3
Accepted
（）
⾸先码⼀下也就是说深搜常常与递归函数或者栈结合使⽤，⽽⼴搜主要和队列结合使⽤。
（1）深度优先搜索（DFS）
当然，这题如果我们当当⽤深搜的话，最终答案会发现超时。所以这就需要我们进⾏剪枝。代码如下：
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <stack>
#include <queue>
using namespace std;
int n,a,b;
int i;
int ans=99999999;
int sum=0;
int k[1000];
int flag[1000];
void DFS(int now_floor,int sum){//now代表现在的楼层，sum代表按按钮的次数
if (now_floor==b) ans=min(ans,sum);
if(sum>ans) return;//⼀个剪枝，属于最优性剪枝，剪枝的含义：如果当前的sum⼤于答案，那么它不可能成为答案。
flag[now_floor]=1;//记录来过当前楼层
if(now_floor+k[now_floor]<=n&&flag[now_floor+k[now_floor]]==0) {
DFS(now_floor+k[now_floor],sum+1);
}
if(now_floor-k[now_floor]>=1&&flag[now_floor-k[now_floor]]==0) {
DFS(now_floor-k[now_floor],sum+1);
}
flag[now_floor]=0;//回溯
}
int main()
{
cin >> n >> a >> b;
for(i=1;i<=n;i++)
cin >> k[i];
flag[a]=1;
DFS(a,sum);
if(ans==99999999) cout <<"-1";
if(ans==99999999) cout <<"-1";
else cout <<ans;
return 0;
}
（2）⼴度优先搜索（BFS）
这⾥转载了洛⾕上⼤佬的做法：
#include <iostream>
#include <queue>
using namespace std;
/************************************************************
⼴度优先搜索算法的基本思想：
1、对于初始状态⼊队，设置初始状态为已访问
2、如果队列不为空时，出队队头元素，否则跳到第5步
3、检查出队的元素是否为最终解，如果是则跳到第5步。
4、对于出队的元素，检查所有相邻状态，如果有效并且未访问，则将
所有有效的相邻状态进⾏⼊队，并且设置这些状态为已访问，然后
跳到第2步重复执⾏
5、检查最后出队的元素是否为最终解，如果是输出结果，否则说明⽆解
⼴度优先搜索是借助于队列这种数据结构进⾏搜索的，队列的特点是先
进先出（FIFO），通过包含queue这个队列模板头⽂件，就可以利⽤c++
的队列模板定义⾃⼰的队列了，队列的操作⾮常简单，主要有以下⼏个：
q.push() ⼊队操作
q.front() 取队头元素
q.pop() 队头元素出队
q.size() 获取队列的元素个数
⼴度优先搜索算法的关键是要搞清楚求解过程中每⼀步的相邻状态有哪些，
每个状态需要记录什么信息，在搜索过程中如何标记这些状态为已访问。
在本题中，相邻状态为当前所在楼层通过按向上或向下按钮所能到达的楼
层，每个状态要记录的信息包括楼层编号和按按钮的次数。
*************************************************************/
//定义队列元素的类型，QElement为结构类型，使⽤typedef可以定义⼀个新的类型名称，在程序中QElement就像int、float⼀样，作为⼀个数据类型的名称使⽤
typedef struct {
int floor; //当前所处的楼层编号
int pushcount; //到达该楼层所经历的步数（按按钮次数）
} QElement;
queue<QElement> q; //定义元素类型为QElement的队列q
int n,a,b;
int s[1000]; //数组s记录每个楼层按按钮后能上下的楼层数
int t[1000]={0}; //数组t记录各个楼层是否已经到达过（已访问过）
int main()
{
QElement e1,e2;
int i;
cin >> n >> a >> b;
for (i=1; i<=n; i++) cin >> s[i];
e1.floor=a;
e1.pushcount=0;
q.push(e1); //初始状态⼊队：当前楼层为a，按按钮次数为0
t[a]=1; //记录当前楼层已访问过
while (!q.empty()) //当队列不为空时，继续宽度优先搜索
{
e2=q.front(); //获取队头元素
q.pop(); //队头元素出队（注意：c++的队列模板类中，获取队头元素并不会将该元素从队列中删除，需要使⽤pop函数删除该元素）
if (e2.floor==b) break; //检查当前状态的楼层编号是否为b，是则说明已经到最终解，跳出循环
i=e2.floor+s[e2.floor]; //按向上按钮后能够到达的楼层
if (i<=n && t[i]==0) //如果按向上按钮能到达的楼层有效并且未访问过该楼层
{
e1.floor=i;
e1.pushcount=e2.pushcount+1;
q.push(e1);
t[i]=1; //设该楼层为已访问过
}
i=e2.floor-s[e2.floor]; //按向下按钮后能够到达的楼层
if (i>=1 && t[i]==0) //如果按向下按钮能到达的楼层有效并且未访问过该楼层
{
e1.floor=i;
e1.pushcount=e2.pushcount+1;
q.push(e1);
t[i]=1; //设该楼层为已访问过
}
}
//如果当前楼层为b，输出按按钮次数，否则⽆解（输出-1）
if (e2.floor==b) cout << e2.pushcount;
else cout << -1;
}
5 168
汉堡包在⼤街上⼤摇⼤摆的⾛着，看着⼿机上⼀道难倒数万⼈的⼩学数学题:
1 + 1 = 0
1 + 6 = 1
6 + 6 = 2
8 + 1 = 2
8 + 6 = 3
汉堡包看完之后发现上⾯这些加法的答案就是看1,6,8中圈圈的个数嘛！
突然之间，所有⼤厦上的LED屏幕上的⼴告全部变成数字1,6,8三个数字的随机闪现。
现给你⼀块n*m的LED屏幕，上⾯有且仅有⼀个数字(1,6,or 8)，请你输出你看见的那个字母。
输⼊格式:
第⼀⾏输⼊两个整数n，m(2<= m, n <= 1000)；
接下来n⾏，每⾏由m个数字0和1组成，其中1表⽰数字1，6，8的组成部分。
输出格式:
输出⼀个整数，代表图形表⽰的数字。
输⼊样例:
7 7
0 0 0 0 0 0 0
0 0 1 1 1 0 0
0 0 1 0 1 0 0
0 0 1 1 1 0 0
0 0 1 0 1 0 0
0 0 1 1 1 0 0
0 0 0 0 0 0 0
输出样例:
8
Accepted
这⼀题的思路主要是我们观察1的数量。如果图形是“1”那么其中1的数量都是相同的，我们记为flag=1
，以此类推，如果图形是“8”那么其中1的数量有两种不同的，我们记为flag=2，如果图形是“6”那么其中1的数量有三种不同的，我们记为flag=3，即可得出答案。
为flag=3，即可得出答案。
具体我们看下⾯的图来理解什么是1的数量：
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <stack>
#include <queue>
using namespace std;
int main(){
int i,j,k=1;
int n,m;
int num[1010]={0};
int num_cmp=0;
int flag=1;
int led[1005][1005];
cin >> n >> m;
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
cin >> led[i][j];
if(led[i][j]==1) num[k]++;
}
if(num[k]!=0)k++;
}
num_cmp=num[k-1];
for(i=k-1;i>0;i--){
if(num[i]<num_cmp) {
flag++;
num_cmp=num[i];字符串长度排序
}
}
if(flag==1) cout <<"1"<<endl;
else if(flag==2) cout <<"8"<<endl;
else cout <<"6"<<endl;
return 0;
}
6 寻宝
奕哥今天玩到⼀款寻宝游戏，地图是⼀个n*m的矩阵，其中分布着⼀些宝藏，每个宝藏具有⼀定的价值，奕哥只能拿⾛其中⼀个宝藏。奕哥起始在a⾏b列。奕哥可以向相邻的⼀格移动，但不能⾛出地图外。奕哥初始体⼒值X，移动⼀格需要消耗体⼒值为1。体⼒耗尽后奕哥⽆法继续移动。地图中有⼀些障
碍物，奕哥⽆法移动到障碍物上。奕哥想知道他能拿到的最具价值的宝藏是哪⼀个。
输⼊格式:
第⼀⾏包含5个整数n,m,a,b,X。n,m分别表⽰地图⾏数，列数；a,b表⽰奕哥起始位置在a⾏b列；X表⽰奕哥的体⼒。（
1<=n,m<=1000, 1<=a<=n, 1<=b<=m, 0<=X<=1e10）
接下来n⾏，每⾏m个整数。第i⾏第j个整数为Aij （-1<=Aij<=1e9）。若Aij=-1，则表⽰第i⾏第j列有障碍物；否则表⽰该位置有⼀个价值为Aij的宝物。保证起始位置没有障碍物。
输出格式:
奕哥能拿到价值最⾼的宝藏的价值。
输⼊样例:
3 3 1 1 3
0 -1 10
3 5 7
-1 8 15
输出样例：
8
Wrong Answer
⼀开始拿到这个题⽬觉得只⽤⽤dfs就可以解决问题，但是发现有⼏个点超时了
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <stack>
#include <queue>
using namespace std;
int n,m,a,b,x;
int p[1005][1005];
int ans=0;
void DFS(int x0,int y0,int x){
if(p[x0][y0]==-1||x==0||x0>n||x0<1||y0>m||y0<1) return ;
ans=max(ans,p[x0][y0]);
DFS(x0-1,y0,x-1);
DFS(x0+1,y0,x-1);
DFS(x0,y0-1,x-1);
DFS(x0,y0+1,x-1);
}
int main()
{
int i,j;
cin >> n >> m >> a >> b >> x;
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
cin >> p[i][j];
}
}
DFS(a,b,x+1);
cout << ans << endl;
return 0;
}
然后我就去⽹上查了⼀些博客，上⾯解答说如果dfs超时了，我们可以采⽤的⽅法。
如何剪枝？
1.最优化剪枝：如果当前已经到的最优路径长度为L ，那么在继续搜索的过程中，总长度已经⼤于等于L的⾛法，就可以直接放
弃，不⽤⾛到底了。
2.可⾏性剪枝：如果当前到达城市的路费已⼤于k，或者等于k且没有到达终点，就可以直接放弃。
很显然，由于我们不知道宝藏最⼤
然后，我就尝试出宝藏中最⼤的那个值，然后如果if(ans==max_) return；但还是会发现超时。这时候，我询问了⼀个同学，才知道我们可以标记⼀下已⾛过的点，如果这个点已经⾛过了，那么我们就不需要重新再⾛，具体代码如下。
Accepted
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <stack>
#include <queue>
using namespace std;
int n,m,a,b,x;
int p[1005][1005];
int flag[1005][1005]={0};
int ans=0;
int ans=0;
void DFS(int x0,int y0,int x){
if(p[x0][y0]==-1||x==0||x0>n||x0<1||y0>m||y0<1||flag[x0][y0]) return ;
ans=max(ans,p[x0][y0]);
flag[x0][y0]=1;
DFS(x0-1,y0,x-1);
DFS(x0+1,y0,x-1);
DFS(x0,y0-1,x-1);
DFS(x0,y0+1,x-1);
}
int main(){
int i,j;
cin >> n >> m >> a >> b >> x;
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
cin >> p[i][j];
}
}
DFS(a,b,x+1);
cout << ans << endl;
return 0;
}
7 龙⾆兰酒吧
有⼀个⼤⼩为n*m的矩形⼩镇，城镇上有房屋（“#”表⽰，⽆法通过），有空地（“.”表⽰，可通⾏），每次移动只能朝上下左右四个⽅向，且需花费1单位时间。
⼀天，⼆乔和承太郎约定在龙⾆兰酒吧见⾯，两⼈同时从各⾃所在位置向酒吧出发。请问最少需要过多少时间他们才能在酒吧碰⾯。
地图上P表⽰⼆乔的位置，W表⽰承太郎的位置，B表⽰酒吧的位置。
输⼊格式:
第⼀⾏包含两个整数n,m，表⽰城镇的⼤⼩。（1<=m,n<=1000)。
接下来n⾏，每⾏m个字符，表⽰⼩镇的情况。
输出格式:
输出两⼈在酒吧碰⾯的最少花费时间，如果⽆法在酒吧碰⾯则输出-1。
输⼊样例:
5 4
.W.#
P#..
....
B..#
#...
输出样例:
4
Wrong Answer
这题我⼀开始⽤了⼴搜然后由于他们是同时出发，取他们两个中花时间最长的⼀个时间就可以了，但是会发现超时了。
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <stack>
#include <queue>
using namespace std;
int n,m;
char p[1005][1005];
int flag[1005][1005]={0};
int ans1=9999,ans2=9999;
int xp,yp,xw,yw;
void DFS1(int x0,int y0,int sum){
if(sum>=ans1||x0<1||x0>n||y0<1||y0>m||p[x0][y0]=='#') return;
if(p[x0][y0]=='B'){
ans1=min(ans1,sum);
}
DFS1(x0-1,y0,sum+1);
DFS1(x0+1,y0,sum+1);
DFS1(x0,y0-1,sum+1);
DFS1(x0,y0+1,sum+1);
}
void DFS2(int x0,int y0,int sum){
if(sum>=ans2||x0<1||x0>n||y0<1||y0>m||p[x0][y0]=='#') return;
if(p[x0][y0]=='B'){
ans2=min(ans2,sum);
}
DFS2(x0-1,y0,sum+1);
DFS2(x0+1,y0,sum+1);
DFS2(x0,y0-1,sum+1);
DFS2(x0,y0+1,sum+1);
}
int main(){
int i,j;
cin >> n >> m ;
getchar();
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
cin >> p[i][j];
if(p[i][j]=='P') {
xp=i;
yp=j;
}
if(p[i][j]=='W') {
xw=i;
yw=j;
}
}
getchar();
}
DFS1(xp,yp,0);
DFS2(xw,yw,0);
if(ans1!=9999&&ans2!=9999) cout << max(ans1,ans2)<< endl;
else cout <<"-1"<<endl;
return 0;
}
Accepted
所以这题需采⽤BFS。(参考：)
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <stack>
#include <queue>
#define P pair<int, int>//pair是将2个数据组合成⼀组数据
using namespace std;
int n,m;
char p[1005][1005];
struct person{
int x0;
int x0;
int y0;
}p1,w1;
int xb=0,yb=0;
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}}; //表⽰x和y可以移动的四个⽅向
const int exmp=999999;
int ansp=0,answ=0;
int bfs(person a){
queue<P> q_new;
int i,j;
int dis[1005][1005]; //保存起点到各点最短距离
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
dis[i][j]=exmp; //将起点到各点的距离初始化为⽆穷⼤，表⽰为到达
}
}
q_new.push(P(a.x0,a.y0));
dis[a.x0][a.y0]=0; //从起点出发将距离设为0 ，并放⼊队列
//不断循环直到队列的长度为0
while(q_new.size()){
//取出队⾸元素
P r=q_new.front();
q_new.pop();
//如果取出的状态是终点，则结束搜索
if(r.first==xb&&r.second==yb) break;
//四个⽅向的循环
for(i=0;i<4;i++){
//移动之后的坐标记为(dx,dy)
int dx=r.first+dir[i][0];
int dy=r.second+dir[i][1];
//判断是否已经访问过，如果dis[dx][dy]不为exmp即为已经访问过
if(dx>0&&dx<=n&&dy>0&&dy<=m&&p[dx][dy]!='#'&&dis[dx][dy]==exmp){ //可以移动的话，则加⼊到队列，并且该位置的距离确定为到r的距离加1 q_new.push(P(dx,dy));
dis[dx][dy]=dis[r.first][r.second]+1;
}
}
}
return dis[xb][yb];
}
int main(){
int i,j;
cin >> n >> m ;
getchar();
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
cin >> p[i][j];
if(p[i][j]=='P') {
p1.x0=i;
p1.y0=j;
}
if(p[i][j]=='W') {
w1.x0=i;
w1.y0=j;
}
if(p[i][j]=='B') {
xb=i;
yb=j;
}
}
getchar();
}
ansp=bfs(p1);
answ=bfs(w1);
if(ansp==exmp||answ==exmp) cout <<"-1"<<endl;
else cout <<max(ansp,answ)<<endl;
return 0;
}
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论