6.5 竞赛题目选讲

6.5 竞赛题目选讲

老生常谈，大家量力而行。

6-17 看图写树 (UVA 10562)

你的任务就是将多叉树转化为括号表达法，就像下面这样：

分析：就是拟态了一个树的样子，其中下面有“|”的字符，就代表为一个根结点。然后输出的话空结点后面跟着一个()，大概就是这样的情况。

这个问题不用想，肯定是要用dfs做的，那我们从哪个角度开始呢？肯定是每层往下面找字符，如果这个字符下面啥都没有就直接输出一对括号，如果这个字符下面有"|“就代表有子树，子书下面一长串的”-"我们把这个横线的长度给找到，就可以对下面的区域进行遍历，如果不是空格，就往下dfs就好了。

代码实现，首先是输入：

#include
#include
using namespace std;
const int maxn=1020;
char tree[maxn][maxn];
int n=0;
int main(){//fgets就是带空格的输入嗷,至于为啥不用getline,getline这里有bug的,有兴趣的可以自己试试看 while (true){fgets(tree[n],maxn,stdin); if (tree[n][0]=='#') break; else n++;}return 0;
} 

(用getline这里容易出问题)

接下来对第一层进行深搜(为啥不对后面的层进行深搜？你在二叉树里做dfs的时候不都是从根结点开始的？)

for (int i=0;i<strlen(tree[0]);i++) if (tree[0][i]!=' ') {dfs(0,i);break;}//别瞎琢磨了,你见过两个root的树?

dfs函数：

void dfs(int r,int c){//r和c都是老朋友了,代表什么大家都懂的printf("%c(",tree[r][c]);//打印父节点if (r+1<n&&tree[r+1][c]=='|'){//表示有子树 int i=c; while (i-1>=0&&tree[r+2][i-1]=='-') i--;//找-字符左边的边界 //其实我个人建议这里顺便把右边的边界也找了得了 while (tree[r+2][i]=='-'&&tree[r+3][i]!='\0'){if (!isspace(tree[r+3][i])) dfs(r+3,i); i++;}		}//这里就是确定有子树,然后慢慢遍历找子节点了 printf(")"); 
}

这里的代码是直接照书打的，有一说一感觉就不是很习惯。

完整代码：

#include
#include
#include//这个大家应该好久没看到了吧 
using namespace std;
const int maxn=1020;
char tree[maxn][maxn];
int n=0;
void dfs(int r,int c){//r和c都是老朋友了,代表什么大家都懂的printf("%c(",tree[r][c]);//打印父节点if (r+1<n&&tree[r+1][c]=='|'){//表示有子树 int i=c; while (i-1>=0&&tree[r+2][i-1]=='-') i--;//找-字符左边的边界 //其实我个人建议这里顺便把右边的边界也找了得了 while (tree[r+2][i]=='-'&&tree[r+3][i]!='\0'){if (!isspace(tree[r+3][i])) dfs(r+3,i); i++;}		}//这里就是确定有子树,然后慢慢遍历找子节点了 printf(")"); 
} 
int main(){//fgets就是带空格的输入嗷,至于为啥不用getline,getline这里有bug的,有兴趣的可以自己试试看 while (true){fgets(tree[n],maxn,stdin); if (tree[n][0]=='#') break; else n++;}for (int i=0;i<strlen(tree[0]);i++) if (tree[0][i]!=' ') {dfs(0,i);break;}//别瞎琢磨了,你见过两个root的树? return 0; 
} 

哎！可以分段写，我就是写一行里，就是玩。

注意测试的时候，那个样例别直接复制粘贴嗷。我们这里看一下测试的结果：

感觉还是不错的(题目的要求里树的两边都是要加括号的)。

6-18 雕塑 (UVA 12171)

给你n个平行于立体坐标系坐标轴的长方体的信息。每个长方体用6个整数x0，y0，z0，x，y，z表示，x0是长方体横坐标的最小值，x表示x方向的总长度，其他四个类似。你的任务就是统计这个雕像的体积和表面积，体积包括内部封闭的空间，表面积的话就不包括。

分析：俗话说的好，听起来越简单的题，做起来就越离谱，你们看起来可能没什么感觉，但是我们来看它原题给的图嗷：

就突出一个阴间。

看了一下数据范围500*500*500，显然不能这样开，然后我们就可以想到之前房屋平面图那个问题，考虑用离散化将数据降为100*100*100(其实还是比较大的)。

那怎么解决这个问题呢?书上是给出了一个粗糙的想法，我解释一下，就是你想啊，有个500*500*500的容器，里面给你放一个雕塑(这里保证了雕塑不会贴着容器)，我们只要将整个容器的体积减去雕塑外围空气的体积，就可以得到这个雕塑的体积，表面积的话，就是外围气体的内表面积。

那具体怎么实现呢？之前不是做过一个连通块嘛，这个问题就等于求离散化外围气体块的连通块。

虽然说了这么多，但是代码实现我是一点底都没有，搜到了一个400+行的代码，差点给电脑扬了，好在后面还是看到一个90行左右的代码，大家和我一起来学习一下(为什么不自己编？你看看我配么？)

最基本的输入：

#include
using namespace std;
const int maxn=55,maxp=1020;//长方体个数的最大值,坐标的最大值
int x0[maxn],y0[maxn],z0[maxn],x1[maxn],y1[maxn],z1[maxn];//0表示起始的值,1表示终止的值 
int main(){int n,lx,ly,lz; scanf("&d",&n);//lx,ly,lz分别代表着长方体三维的长度 for (int i=0;i<n;i++){scanf("%d%d%d%d%d%d",&x0[i],&y0[i],&z0[i],&lx,&ly,&lz);x1[i]=x0[i]+lx; y1[i]=y0[i]+ly; z1[i]=z0[i]+lz;//终止位置 }return 0; 
}

离散化：

#include
#include 
using namespace std;
const int maxn=55,maxp=1020;//长方体个数的最大值,坐标的最大值
int x0[maxn],y0[maxn],z0[maxn],x1[maxn],y1[maxn],z1[maxn];//0表示起始的值,1表示终止的值
int xs[2*maxn],ys[2*maxn],zs[2*maxn]; //离散化后的坐标 
int nx,ny,nz;//分别用于记录离散化后的数组长度
//离散化,就是给原数组先排个序,再去个重复 
void discretize(int*a,int&n){sort(a,a+n); n=unique(a,a+n)-a;} 
int main(){int n,lx,ly,lz; scanf("&d",&n);//lx,ly,lz分别代表着长方体三维的长度 xs[0]=0; ys[0]=0; zs[0]=0; xs[1]=maxp; ys[1]=maxp; zs[1]=maxp;//定义外围边界 nx=ny=nz=2;//当前的长度 for (int i=0;i<n;i++){scanf("%d%d%d%d%d%d",&x0[i],&y0[i],&z0[i],&lx,&ly,&lz);x1[i]=x0[i]+lx; y1[i]=y0[i]+ly; z1[i]=z0[i]+lz;//终止位置xs[nx++]=x0[i]; xs[nx++]=x1[i]; //离散化准备ys[ny++]=y0[i]; ys[ny++]=y1[i];zs[nz++]=z0[i]; zs[nz++]=z1[i]; }//离散化 discretize(xs,nx); discretize(ys,ny); discretize(zs,nz); return 0; 
}

这个看不懂的就回顾回顾前面的章节吧，当时讲的很细了。

接下来对铜块和空气块进行标记，首先我们先看一个函数：

//这个函数用于获取val在长为n的a数组中的位置 
int getId(int*a,int n,int val){return lower_bound(a,a+n,val)-a;}

这个lower_bound原博主说就是查找，但我越想越觉得奇怪，查找为什么要用lower呢？然后我就去搜了一下，下面是标准的解释：

lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

(upper的话大家类比一下就知道是什么用处了)

我们离散化的数组不是一个升序的数组嘛，找到大于等于num的数实际上就等于找到这个数了，所以这里的解释是查找到这个数的意思。

标记：

memset(color,0,sizeof(color));for (int i=0;i<n;i++){//根据x0的值去标记大铜块 int X0=getId(xs,nx,x0[i]),X1=getId(xs,nx,x1[i]);//获取位置 int Y0=getId(ys,ny,y0[i]),Y1=getId(ys,ny,y1[i]);int Z0=getId(zs,nz,z0[i]),Z1=getId(zs,nz,z1[i]);//标记大铜块,X0-X1,Y0-Y1,Z0-Z1里面的块肯定是小铜块 for (int x=X0;x<X1;x++) for (int y=Y0;y<Y1;y++) for (int z=Z0;z<Z1;z++) color[x][y][z]=1; }

其实我个人觉得这里时间复杂度是比较高的，因为这里做了一个查找。以我个人的经验(不是指这道题)，像这种排序以后，还要得到原本数位置的问题，我一般都是定义一个结构体，假设叫node吧。里面定义两个成员变量，value表示数值，pos表示当前的位置，在输入的时候就是0到n-1。在排序的时候，对sort函数的cmp函数进行一个改写，就是比较node.value的大小，对value进行排序后，pos就是我们需要的原本在数组中的位置。

至于你问我为什么不改写，俗话说的好：可以完成需求的代码，你就别乱改。

接下来就是bfs了(这个我也很吃惊啊，发现别人是用bfs不是用dfs做的)。

首先是定义结点的结构体，它这里就直接把很多功能都封装进去了：

初始化：

int x,y,z;//用来bfs的坐标,表示长方体的左下角Cell (int _x,int _y,int _z):x(_x),y(_y),z(_z){}//构造函数

判断是否越界：

//判断是否出现越界的情况,这个我们上一章节就接触过了 bool isValid(){return (0<=x&&x<nx-1)&&(0<=y&&y<ny-1)&&(0<=z&&z<nz-1);}

bfs的方向数组和找子节点：

//bfs的六个方向 
int dirt[6][3]={{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};
//这就是找子节点呗 
Cell getNeighbor(int dir){return Cell(x+dirt[dir][0],y+dirt[dir][1],z+dirt[dir][2]);}

计算体积：

int getVolume(){return (xs[x+1]-xs[x])*(ys[y+1]-ys[y])*(zs[z+1]-zs[z]);}//计算块的体积

表面积的计算，因为牵扯到它对照的是x轴，y轴还是z轴，所以是比较复杂的：

int getArea(int dir){//表面积的计算是需要通过这个块的方向得到的//首先有一点是可以确定的,就是方向数组里的三元组,只有一个不为0,其他的都是0//那不为0代表着什么呢?就是代表这个结点,也就是方块//它的父结点,我们这里就叫父方块吧,和它接触的面//第一个就是x方向,第二个是y方向,第三个是z //这里的dir应该指的就是当前方块和空气接触的面的序号//x方向面接触的,那表面积就是y方向的长度乘以z方向的长度,另外两个方向同理 if (dirt[dir][0]) return(ys[y+1]-ys[y])*(zs[z+1]-zs[z]);else if (dirt[dir][1]) return (xs[x+1]-xs[x])*(zs[z+1]-zs[z]);else if (dirt[dir][2]) return (xs[x+1]-xs[x])*(ys[y+1]-ys[y]);return -1;//表示出错}

三个判断：

bool isCopper(){return color[x][y][z]==1;} //判断是否为铜块bool isVisited() {return color[x][y][z]==2;} //判断是否为被访问过的空气块 void setVisited() {color[x][y][z]=2;} //将空气块设置为已访问 

完整的结构体：

struct Cell{//他说的什么逻辑上的长方体,你往树里想就是结点 int x,y,z;//用来bfs的坐标,表示长方体的左下角Cell (int _x,int _y,int _z):x(_x),y(_y),z(_z){}//构造函数//判断是否出现越界的情况,这个我们上一章节就接触过了 bool isValid(){return (0<=x&&x<nx-1)&&(0<=y&&y<ny-1)&&(0<=z&&z<nz-1);}//这就是找子节点呗 Cell getNeighbor(int dir){return Cell(x+dirt[dir][0],y+dirt[dir][1],z+dirt[dir][2]);}int getVolume(){return (xs[x+1]-xs[x])*(ys[y+1]-ys[y])*(zs[z+1]-zs[z]);}//计算块的体积 int getArea(int dir){//表面积的计算是需要通过这个块的方向得到的//首先有一点是可以确定的,就是方向数组里的三元组,只有一个不为0,其他的都是0//那不为0代表着什么呢?就是代表这个结点,也就是方块//它的父结点,我们这里就叫父方块吧,和它接触的面//第一个就是x方向,第二个是y方向,第三个是z //这里的dir应该指的就是当前方块和空气接触的面的序号//x方向面接触的,那表面积就是y方向的长度乘以z方向的长度,另外两个方向同理 if (dirt[dir][0]) return(ys[y+1]-ys[y])*(zs[z+1]-zs[z]);else if (dirt[dir][1]) return (xs[x+1]-xs[x])*(zs[z+1]-zs[z]);else if (dirt[dir][2]) return (xs[x+1]-xs[x])*(ys[y+1]-ys[y]);return -1;//表示出错}bool isCopper(){return color[x][y][z]==1;} //判断是否为铜块bool isVisited() {return color[x][y][z]==2;} //判断是否为被访问过的空气块 void setVisited() {color[x][y][z]=2;} //将空气块设置为已访问 
};

接下来就到bfs了：

//bfs函数
//还是要强调一遍,这里bfs是找空气的连通块,也就是说是根据空气bfs的 
void bfs(int&v,int&m){//先建立一个队列和一个根结点 queue<Cell>q; q.push(Cell(0,0,0)); color[0][0][0]=2;while (!q.empty()){//进一个出一个,bfs的基本格式都是 Cell cell=q.front(); q.pop();v+=cell.getVolume();//累加体积,注意是空气的体积 for (int i=0;i<6;i++){//对六个方向进行bfs Cell neb=cell.getNeighbor(i);//获取"邻居",个人看就是子节点 if (neb.isValid()){//先判断一下是否越界 //如果是铜块的话,我们就根据和空气接触的方向,来计算表面积的大小 if (neb.isCopper()) m+=cell.getArea(i);//表面积进行累加 //接下来就是找没有访问过的空气快将他加入队列,同时记得设置为已访问 else if (!neb.isVisited()){neb.setVisited();q.push(neb);}}}}v=(maxp*maxp*maxp)-v;//铜块体积=总体积-空气体积
}

一定要记得这里bfs找的是空气的连通块，我自己写的时候就经常绕不过来。

完整代码如下：

#include
#include
#include
#include 
using namespace std;
const int maxn=55,maxp=1001;//长方体个数的最大值,坐标的最大值
int x0[maxn],y0[maxn],z0[maxn],x1[maxn],y1[maxn],z1[maxn];//0表示起始的值,1表示终止的值
int xs[2*maxn],ys[2*maxn],zs[2*maxn];//离散化后的坐标 
//bfs的六个方向 
int dirt[6][3]={{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}}; 
int nx,ny,nz;//分别用于记录离散化后的数组长度
int color[maxn*2][maxn*2][maxn*2];//标记块的情况,0为空气,1为铜块,2为访问过的空气
//这个函数用于获取val在长为n的a数组中的位置 
int getId(int*a,int n,int val){return lower_bound(a,a+n,val)-a;} 
//离散化,就是给原数组先排个序,再去个重复 
void discretize(int*a,int&n){sort(a,a+n); n=unique(a,a+n)-a;}
struct Cell{//他说的什么逻辑上的长方体,你往树里想就是结点 int x,y,z;//用来bfs的坐标,表示长方体的左下角Cell (int _x,int _y,int _z):x(_x),y(_y),z(_z){}//构造函数//判断是否出现越界的情况,这个我们上一章节就接触过了 bool isValid(){return (0<=x&&x<nx-1)&&(0<=y&&y<ny-1)&&(0<=z&&z<nz-1);}//这就是找子节点呗 Cell getNeighbor(int dir){return Cell(x+dirt[dir][0],y+dirt[dir][1],z+dirt[dir][2]);}int getVolume(){return (xs[x+1]-xs[x])*(ys[y+1]-ys[y])*(zs[z+1]-zs[z]);}//计算块的体积 int getArea(int dir){//表面积的计算是需要通过这个块的方向得到的//首先有一点是可以确定的,就是方向数组里的三元组,只有一个不为0,其他的都是0//那不为0代表着什么呢?就是代表这个结点,也就是方块//它的父结点,我们这里就叫父方块吧,和它接触的面//第一个就是x方向,第二个是y方向,第三个是z //这里的dir应该指的就是当前方块和空气接触的面的序号//x方向面接触的,那表面积就是y方向的长度乘以z方向的长度,另外两个方向同理 if (dirt[dir][0]) return(ys[y+1]-ys[y])*(zs[z+1]-zs[z]);else if (dirt[dir][1]) return (xs[x+1]-xs[x])*(zs[z+1]-zs[z]);else if (dirt[dir][2]) return (xs[x+1]-xs[x])*(ys[y+1]-ys[y]);return -1;//表示出错}bool isCopper(){return color[x][y][z]==1;} //判断是否为铜块bool isVisited() {return color[x][y][z]==2;} //判断是否为被访问过的空气块 void setVisited() {color[x][y][z]=2;} //将空气块设置为已访问 
};
//bfs函数
//还是要强调一遍,这里bfs是找空气的连通块,也就是说是根据空气bfs的 
void bfs(int&v,int&m){//先建立一个队列和一个根结点 queue<Cell>q; q.push(Cell(0,0,0)); color[0][0][0]=2;while (!q.empty()){//进一个出一个,bfs的基本格式都是 Cell cell=q.front(); q.pop();v+=cell.getVolume();//累加体积,注意是空气的体积 for (int i=0;i<6;i++){//对六个方向进行bfs Cell neb=cell.getNeighbor(i);//获取"邻居",个人看就是子节点 if (neb.isValid()){//先判断一下是否越界 //如果是铜块的话,我们就根据和空气接触的方向,来计算表面积的大小 if (neb.isCopper()) m+=cell.getArea(i);//表面积进行累加 //接下来就是找没有访问过的空气快将他加入队列,同时记得设置为已访问 else if (!neb.isVisited()){neb.setVisited();q.push(neb);}}}}v=(maxp*maxp*maxp)-v;//铜块体积=总体积-空气体积
} 
int main(){int n,lx,ly,lz; scanf("&d",&n);//lx,ly,lz分别代表着长方体三维的长度 xs[0]=0; ys[0]=0; zs[0]=0; xs[1]=maxp; ys[1]=maxp; zs[1]=maxp;//定义外围边界 nx=2;ny=2;nz=2;//当前的长度 for (int i=0;i<n;i++){scanf("%d%d%d%d%d%d",&x0[i],&y0[i],&z0[i],&lx,&ly,&lz);x1[i]=x0[i]+lx; y1[i]=y0[i]+ly; z1[i]=z0[i]+lz;//终止位置xs[nx++]=x0[i]; xs[nx++]=x1[i]; //离散化准备ys[ny++]=y0[i]; ys[ny++]=y1[i];zs[nz++]=z0[i]; zs[nz++]=z1[i]; }//离散化 discretize(xs,nx); discretize(ys,ny); discretize(zs,nz);memset(color,0,sizeof(color));for (int i=0;i<n;i++){//根据x0的值去标记铜块 int X0=getId(xs,nx,x0[i]),X1=getId(xs,nx,x1[i]);//获取位置 int Y0=getId(ys,ny,y0[i]),Y1=getId(ys,ny,y1[i]);int Z0=getId(zs,nz,z0[i]),Z1=getId(zs,nz,z1[i]);//标记铜块,X0-X1,Y0-Y1,Z0-Z1里面的块肯定是铜块 for (int x=X0;x<X1;x++) for (int y=Y0;y<Y1;y++) for (int z=Z0;z<Z1;z++) color[x][y][z]=1; }//体积和面积 int v=0,m=0; bfs(v,m); printf("%d %d",v,m);//通过floodfill去求连通块return 0; 
}

(虽然不知道为什么，但是这里的代码是有一点小问题的，等我咨询完老师会第一时间过来修改这个问题)

当然我还是比较推荐大家去看人家原本的代码，然后自己写一遍，原代码出自：UVA 12171的解决

6-19 自组合 (UVA 1572)

给你n种正方形，正方形有四条边组成。每个边上有一个标号，要么为一个大写字母加上一个加号或者减号，要么为数字00。其中两条边字母相同且符号相反时，两条边可以拼在一起(00就是死边，什么都不可以拼)。

每一种正方形都有无数个，并且都可以翻转或者旋转，需要你判断能否组成一个无限大的结构，每条边要么不和任何其他边相邻，要么可以和上述的一条边相邻。

分析：这道题光理解就花了我一段时间，按照我的理解就是，能否组成一个结构，可以无限地拼接其他的方块。

那什么样地结构才可以无限延伸呢？如果一直不断地拼接方块，然后在这个结构悬空的边中找可以拼接的边，这样做显然是得不到的答案的。

看了一下n的数据非常大，说明这里树的枝肯定和n没什么关系。我们可以将每一方块转化为若干个标号的联系，比如说方块：A-B+00D+，由于B+可以和B-拼接，也就是说A-和B-，D+和B-都建立起了联系。

因为A+到Z+，A-到Z-总共有52种标号，我们可以通过三重循环的方式得到所有的连通路(1->2，2->3合并为1->3，我突然发现这个在离散二元关系那课是有教过的)。

接下来的一步我想了很久才明白。那我们怎么确定一种结构可以无限延伸呢？我假设这个结构最原始形态为n种给定的正方形每个各一个，所含的标号的种类为集合为X[0]，我们以X[0]中的每一个元素为一个树的根节点，往下找子节点，子节点就是和当前标号有联系的标号，就是我们上面得到的若干个联系。

那无限延伸是一个什么样的情况呢？就是这些树中，至少存在一个树，它的每一层结点都至少存在一个节点可以作为父节点继续往下找子节点。

因为是无限的，所以回溯到根结点，找这条"路径"。它的长度至少一定大于52吧，也就是在这条"路径"中，一定有可以两个相同的标号。这意味着，一定存在某个标号，可以通过自己访问到自己，也就是形成了一个环。

其实如果我们知道联系中存在一个环的话，我们不断循环这个环的路径，也确实可以得到一个无限长的结构。这样充分性和必要性我们就都得到了。

结合离散数学总结一下，就是说，我们通过n个方块自己的四条边，先初始地搭建一个二元关系的关系矩阵，然后使用Warshall算法得到这个关系矩阵的传递闭包。然后判断这个闭包的对角线上有没有一个为1，如果为1就代表着是一个可以无限延伸的结构。

代码实现：

#include
#include
using namespace std;
int con[55][55];//关系矩阵 
//将标号转化为数字 
int string_node(string s){ if(s=="00") return -1;//比较简单就自己体会吧 int node=s[0]-'A'; return node*2+(s[1]=='+');
}
int main(){memset(con,0,sizeof(con)); int n,node[6]; cin>>n; string s;//node组表示四条边的标号 for (int i=0;i<n;i++){cin>>s; for(int j=0;j<4;j++) node[j]=string_node(s.substr(j*2,2));//提取标号//建立最开始的关系矩阵 for (int j=0;j<4;j++) for (int k=0;k<4;k++) if(node[j]!=-1&&node[k]!=-1&&j!=k) con[node[j]][node[k]^1]=1;//这里的^1就是将二进制下的最后一位进行了改变//我也是看了别人的代码才知道有这种巧妙的处理方法的 }int flag=0; //进行Warshall算法的运算来得到传递闭包 for(int i=0;i<51;i++) for(int j=0;j<51;j++) for(int k=0;k<51;k++) con[i][j]|=con[i][k]&&con[k][j];for (int i=0;i<51;i++) flag|=con[i][i];//确定有没有环if (flag) cout<<"unbounded"; else cout<<"bounded";return 0;
}

本来完全是自己写的代码，然后网上搜了一下，发现很多细节处理得不够优雅，就学习了人家的一些东西。可以看得出，这个算法实现的是非常优雅的和好看的。

6-20 理想路径 (UVA 1599)

给一个n个点m条边的无向图，每条边涂有一种颜色，求从结点1到结点n的一条路径，要求经过的边数尽量少的基础上，经过边的颜色序列的字典序最小。

分析：这个问题乍一看，就是个最短路的问题，bfs一下，bfs的规则稍微改动一下，就是如果每次有多条路线，就是有多个结点，将颜色字典序小的子结点先放入队列。得到结点n以后不停地往前找父节点就可以了。

关键这里提了一种方法说是无需记录父结点，就是反向的BFS，而且只需要做一遍bfs，我搜了半天也没看到一个代码是这么做的(网上的代码基本都是做了两次bfs)。

所以这个问题就先搁置在这里，至于存父结点的那个方法，翻看前面的章节就可以了，就不重复介绍了(主要是书上说那个双向bfs非常重要，所以还是打算弄明白了，主要介绍那个方法)。

6-21 系统依赖 (UVA 506)

题面请点击这里

分析：难是不算太难，就是非常的ex，我分步给大家讲一下。

首先是建立依赖的联系：

//用于建立软件和依赖的软件的关系 
map<string,vector<string> >item_depend;
//表示当前软件的状态
map<string,int>item_stat; 
void create_link(string s){//按照空格分割字符串 stringstream SS(s); string item,item1; int num=0;while (getline(SS,item,' ')){num++;//第一个字符串是DEPEND if (num==2) item1=item;//当num大于2的时候就是依赖的组件 else if (num>2){item_depend[item1].push_back(item);}if (num>1) item_stat[item]=0;//表示未安装 }
}

分割字符串就不多说了，这里是用string和vector的映射，去得到组件和需要依赖的组件的映射。

然后是安装：

void install(string s){//安装 stringstream SS(s); string item; int num=0;while (getline(SS,item,' ')){num++;//已经安装过了 if (num>1&&item_stat[item]) cout<<"\t"<<item<<" is already installed.\n";else if (num>1&&!item_stat[item]){//只要说明了的安装都是显性安装for (vector<string>::iterator i=item_depend[item].begin();i!=item_depend[item].end();i++){if (!item_stat[*i]) cout<<"\tInstalling "<<*i<<endl; item_stat[*i]+=2;} item_stat[item]+=1; cout<<"\tInstalling "<<item<<endl;//安装完毕 //进行显性安装会给显性安装的组件+1,隐性则+2 } }
}

只有状态是0才可以安装，安装的时候如果是一个有依赖的组件(就是map中找得到的key)，我们还要把没有安装过的依赖给安装了(我这里为什么没有做判断？大家可以想一下这个问题)。那为什么这里是+2呢？就是考虑到很多组件不止被一个组件依赖，所以不能单单的改成2(我最开始的时候就是改成2)，然后每次卸载依赖它的组件减去2就可以了。

卸载：

void remove(string s){//删除 stringstream SS(s); string item; int num=0;while (getline(SS,item,' ')){num++;if (num>1){//遍历一遍依赖,如果它只被要卸载的软件依赖,那直接卸了是没什么问题的//如果状态值大于2,说明被多个组件依赖,那就不能进行卸载//但是会减弱它的依赖性, 就是状态值-2//如果是被依赖的,就不能进行卸载了 //如果没有被安装的,是无法进行卸载的,需要进行提醒 if (item_stat[item]>=2) {cout<<"\t"<<item<<" is still needed.\n"; break;}if (!item_stat[item]) {cout<<"\t"<<item<<" is not installed.\n"; break;}for (vector<string>::iterator i=item_depend[item].begin();i!=item_depend[item].end();i++){item_stat[*i]-=2; if(!item_stat[*i]) cout<<"\tRemoving "<<*i<<endl;}cout<<"\tRemoving "<<item<<endl;}}
} 

其实主要的就是削弱一遍依赖的组件的依赖性，如果直接变为0了，就给它卸了，如果没变为0，说明还在哪里用着，就不能卸(这里的细节特别多)。

list(这个应该是最简单的一个函数)：

void list(){//列举已经安装的组件 for (map<string,int>::iterator i=item_stat.begin();i!=item_stat.end();i++)if (i->second) cout<<"\t"<<i->first<<endl;
}

就遍历一遍就行了，完整代码如下：

#include
#include
#include
#include
#include
using namespace std;
//用于建立软件和依赖的软件的关系 
map<string,vector<string> >item_depend;
//表示当前软件的状态
map<string,int>item_stat; 
void create_link(string s){//按照空格分割字符串 stringstream SS(s); string item,item1; int num=0;while (getline(SS,item,' ')){num++;//第一个字符串是DEPEND if (num==2) item1=item;//当num大于2的时候就是依赖的组件 else if (num>2){item_depend[item1].push_back(item);}if (num>1) item_stat[item]=0;//表示未安装 }
}
void install(string s){//安装 stringstream SS(s); string item; int num=0;while (getline(SS,item,' ')){num++;//已经安装过了 if (num>1&&item_stat[item]) cout<<"\t"<<item<<" is already installed.\n";else if (num>1&&!item_stat[item]){//只要说明了的安装都是显性安装for (vector<string>::iterator i=item_depend[item].begin();i!=item_depend[item].end();i++){if (!item_stat[*i]) cout<<"\tInstalling "<<*i<<endl; item_stat[*i]+=2;} item_stat[item]+=1; cout<<"\tInstalling "<<item<<endl;//安装完毕 //进行显性安装会给显性安装的组件+1,隐性则+2 } }
}
void remove(string s){//删除 stringstream SS(s); string item; int num=0;while (getline(SS,item,' ')){num++;if (num>1){//遍历一遍依赖,如果它只被要卸载的软件依赖,那直接卸了是没什么问题的//如果状态值大于2,说明被多个组件依赖,那就不能进行卸载//但是会减弱它的依赖性, 就是状态值-2//如果是被依赖的,就不能进行卸载了 //如果没有被安装的,是无法进行卸载的,需要进行提醒 if (item_stat[item]>=2) {cout<<"\t"<<item<<" is still needed.\n"; break;}if (!item_stat[item]) {cout<<"\t"<<item<<" is not installed.\n"; break;}for (vector<string>::iterator i=item_depend[item].begin();i!=item_depend[item].end();i++){item_stat[*i]-=2; if(!item_stat[*i]) cout<<"\tRemoving "<<*i<<endl;}cout<<"\tRemoving "<<item<<endl;}}
}
void list(){//列举已经安装的组件 for (map<string,int>::iterator i=item_stat.begin();i!=item_stat.end();i++)if (i->second) cout<<"\t"<<i->first<<endl;
} 
int main(){while (true){//非常基本的输入 string s; getline(cin,s); if (s[0]=='E') break;cout<<s<<endl;//表明正在做这个指令 switch (s[0]){case 'D': create_link(s);break;case 'I': install(s);break;case 'R': remove(s);break;case 'L': list();break; }}return 0; 
}

这个完全是自己写的，所以不确定正确性(测试是过了)，如果有错误的欢迎大家给我指出(不欢迎，不想改)。

6-22 战场 (UVA 11853)

一堆人玩水弹，知道他们的坐标和攻击范围，问你从西边到东边能否不被水弹砸。找出西边进入的位置和东边出去的位置。

分析：很简单的一个问题，问能否从西边"安然无恙"地到东边，不就是问从南边到北边，存不存在若干个连续的"弹坑"把从西到东地路给堵住了嘛。那这不就是个bfs吗？

代码实现如下：

#include
#include
using namespace std;
struct danger{//bfs的结点 double x,y,r; bool is_linked;danger (double x=0,double y=0,double r=0,bool is_linked=false):x(x),y(y),r(r),is_linked(is_linked){}; 
}root(true),a[101];//根结点
bool if_linked(danger A,danger B){//判断是否可以作为子节点 if ((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y)>A.r+B.r) return false; else return true;
} 
int n;
bool bfs(){//bfs函数 queue<danger>q; q.push(root);while (!q.empty()){danger u=q.front(); q.pop();if (u.x+u.r>=1000) return true;//表示路被"堵上"了 for (int i=0;i<n;i++) if (if_linked(u,a[i])&&!a[i].is_linked){a[i].is_linked=true;q.push(a[i]);} //找子节点 }return false;
}
int main(){cin>>n;for (int i=0;i<n;i++){double x,y,r; cin>>x>>y>>r; a[i]=danger(x,y,r);}if(bfs()) cout<<"Impossible"; else cout<<"Possible";return 0;
}

这个依旧是自己打的代码，欢迎大家帮我检查一下。

那有人要问题目不是要你在possible的时候，输出东边和西边的坐标么？你仔细地想一下，如果中间没有堵塞，那东边和西边不是只要顺着坐标轴，找他们纵坐标最大的情况不就好了。这个就交给大家自己去实现了(这个真的非常简单)。

一些想说的话

从前一天七点多忙到现在四点半的样子，中间没有睡觉和吃饭。当然有很多人始终在宣扬"算法无用论"(我个人也是这么觉得的？)，就像我在做这个章节的时候，很多情况下也是优先去搜别人的代码去看，那到做事的时候直接把别人的包，别人的东西拿过来用不就好了。

确实很难说去反对这种想法，因为确实别人的代码都写的非常的优雅，非常的好看，自己写代码的话，很多bug，很多要调试的地方，代码也很丑。而且对于很多问题或者项目，博客园，GitHub都已经给出了一些优化的非常好的代码，就像你用Mysql，你也不太会去纠结他底层的原理，有的时候我们只需要说知道怎么用就可以了。

但是说当我们真正地去花了一定的时间，去理解，编写一些我们从前没有学过的，写过的东西，去理解新的处理问题的方法或者说一些优雅地编程方式和小技巧。这种经验和收获感是难能可贵的。

我和我的朋辈们，都是大一大二的学生，但是有的人已经走了很远的路，而有的人像我至今对知识，对自己未来的方向，都是浅尝辄止的了解。我们大多时候不能确定，现在学的东西对未来到底有没有用或者功利一点说能不能帮我们赚钱。仔细想来发现人生亦是如此。

我们太多人总是想着找到一个人生的"最优解"，然后在快步人生的旅途中不停地更改着我们的方向。回望过去，有时也会发现不是"最优解"真正成就了现在的我们，而是曾经无意中做过的一些小事，学过的一些小知识，很可惜地却是再回忆，已是零零碎碎的片段了。

但毋庸置疑的是，无论无论在哪些方向，我们与我们的朋辈，都已经走了不少的路，且无论你是否愿意都将继续走下去。突然想到，一句高中语文老师经常提过的课本上的一句话，当时始终没有明白，希望现在提起不是不合时宜。

慢慢走，欣赏啊！

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！