BFS和sscanf的用法
1.东东有一张地图，想通过地图找到妹纸。地图显示，0表示可以走，1表示不可以走，左上角是入口，右下角是妹纸，这两个位置保证为0。请你编一个程序，写出东东找到妹纸的最短路线。
输入是一个5 × 5的二维数组，仅由0、1两数字组成，表示法阵地图。
输出若干行，表示从左上角到右下角的最短路径依次经过的坐标。数据保证有唯一解。
分析
’定义一个点结构
struct point{ int x,y; }
BFS一层层向外（终点）蔓延
void bfs(point start){
queue q;
q.push(start);
b[0][0]=0;a[0][0]=1;
while(!q.empty()){
newp=q.front();
q.pop();
for(int i=0;i-1&&next.x-1&&next.yb[newp.x][newp.y]+1)
b[next.x][next.y]=b[newp.x][newp.y]+1;//记录到原点最近距离
}
}
}
}
stepx和stepy数组是下一个点的偏移量。每遍历一个未到过的点，记录到该点的最近距离。
输出:可以从终点向原点遍历记录每个坐标然后输出。假设当前点到原点距离为l，上一个点到原点距离一定是l-1，且该点在当前点的周围。一层层忘回遍历，就能得到最短路径每个点坐标。
for(int i=0;i-1&&next.x-1&&next.y<5){
dest.x=next.x;dest.y=next.y;
sp[l].x=next.x;sp[l].y=next.y;
break;
}
}
2.倒水问题 “fill A” 表示倒满A杯，"empty A"表示倒空A杯，“pour A B” 表示把A的水倒到B杯并且把B杯倒满或A倒空。
输入：输入包含多组数据。每组数据输入 A, B, C 数据范围 0 < A <= B 、C <= B <=1000 、A和B互质。
输出：你的程序的输出将由一系列的指令组成。这些输出行将导致任何一个罐子正好包含C单位的水。每组数据的最后一行输出应该是“success”。输出行从第1列开始，不应该有空行或任何尾随空格。
分析
现在考虑三种情况：
杯子中有水：倒空
杯子中水未满：倒满
A中水未满，B中有水：A倒满或B倒空（或者说有一个杯子倒满或有一个杯子倒空）
把AB杯子的水看做坐标，要找到（任意，C）和（C，任意）
void bfs(int a,int b,int c){
state f,news;
f.x=0;f.y=0;
q.push(f);
d=0;
while(!q.empty()){
f=q.front();
q.pop();
if(f.x==c||f.y==c){//边界
prt(f);//输出
return;
}
if(f.x>0)
{
news.x=0;news.y=f.y;
updt(f,news);
}
if(f.y>0){
news.x=f.x;news.y=0;
updt(f,news);//倒空，更新新的点
}
if (f.x<=a)
{
news.x=a;
news.y=f.y;
updt(f,news);
}
if (f.x<=a&&f.y!=0)
{
if (f.x+f.y<=a)
{
news.x=f.x+f.y;
news.y= 0;
updt(f,news);
} else
{
news.x=a;
news.y=f.x+f.y-a;
updt(f,news);
}
}
//x类似
}
}
}
输出
知道两个点（两个状态），可以推断出当前状态进行了那个变化（刚刚讨论的三种情况）
if(f.x!=newss.x&&f.y!=newss.y){
if(f.x<newss.x){
cout<<"pour A B"<<endl;
}
else{
cout<<"pour B A"<<endl;
}
}
else{
if(f.x==newss.x){
if(f.y==0){
cout<<"empty B"<<endl;
}
else{
cout<<"fill B"<<endl;
}
}
else{
if(f.x==0){
cout<<"empty A"<<endl;
}
else{
cout<<"fill A"<<endl;
}
}
}
化学很神奇，以下是烷烃基。
假设如上图，这个烷烃基有6个原子和5个化学键，6个原子分别标号1~6，然后用一对数字 a,b 表示原子a和原子b间有一个化学键。这样通过5行a,b可以描述一个烷烃基
你的任务是甄别烷烃基的类别。
分析
同一个原子可能有不同编号，如果硬钢这道题很复杂。
观察每个分子的独有特点，第一个没有一个原子边（与其他原子的连线）大于等于3，第二个和第三个有一个等于3.第四个有两个等于3，第五个有一个等于4.
记录等于三和等于四的个数three four，可以区分出1、4、5.
然后观察2和3，第二个分子中，与边为三的原子相连的原子有两个边为1。第三个中，与边为三的原子相连的原子有一个边为1。
先记录一下边
for(int i=0;i>x>>y;
a[x][0]++;a[y][0]++;
a[x][y]=1;a[y][x]=1;
}
区分每个分子
void maze(){
int four=0,three=0,one=0,node;
for(int i=1;i<7;i++){
if(a[i][0]==3){
three++;
node=i;
}
else{
if(a[i][0]==4){
four++;
}
}
}
if(three==1){
for(int i=1;i<7;i++){
if(a[node][i]==1&&a[i][0]==1){
one++;
}
}
if(one==1){
cout<<s[2]<<endl;//第三个
}
else{
cout<<s[1]<<endl;//第二个
}
}
else{
if(three==2){
cout<<s[3]<<endl;//第四个
}
else{
if(four==1){
cout<<s[4]<<endl;//第五个
}
else
cout<<s[0]<<endl;//第一个
}
}
}
4.例如某次考试一共八道题（A,B,C,D,E,F,G,H），每个人做的题都在对应的题号下有个数量标记，负数表示该学生在该题上有过的错误提交次数但到现在还没有AC，正数表示AC所耗的时间，如果正数a跟上了一对括号，里面有个正数b,则表示该学生AC了这道题，耗去了时间a，同时曾经错误提交了b次。例子可见下方的样例输入与输出部分。
输入输出：输入数据包含多行，第一行是共有的题数n（1≤n≤12）以及单位罚时m（10≤m≤20），之后的每行数据描述一个学生的信息，首先是学生的用户名（不多于10个字符的字串）其次是所有n道题的得分现状，其描述采用问题描述中的数量标记的格式，见上面的表格。
根据这些学生的得分现状，输出一个实时排名。实时排名显然先按AC题数的多少排，多的在前，再按时间分的多少排，少的在前，如果凑巧前两者都相等，则按名字的字典序排，小的在前。每个学生占一行，输出名字（10个字符宽），做出的题数（2个字符宽，右对齐）和时间分（4个字符宽，右对齐）。名字、题数和时间分相互之间有一个空格。数据保证可按要求的输出格式进行输出。
分析
这道题的输入比较麻烦。
可以把每道题的结果输入到string或char结构中，然后再对每一个string或char进行处理。
处理有两种方法：第一种，对字符串处理，去除 ‘（ ’ 和 ‘ ）’，剥离出数据，再进行计算。
与第一种相比，第二种比较巧妙（也是本次实验的一大收获）。使用函数sscanf（VS2019会提示该函数不安全，用sscanf_s代替即可），sscanf会返回参数个数，失败返回0。
举个例子：sscanf(“10,10”,"%d,%d",&a,&b); 根据格式把10输入到ab中。
回到本题，利用sscanf返回的参数处理字符串，返回一个参数说明是AC（a是时间）或a<=0。
返回两个参数，a是时间，b是错误次数。time=a+b*m；
while (cin >> name)
{
sdu[k].name = name;sdu[k].num = 0; sdu[k].time = 0;
for (int i = 0; i > s;
if (sscanf_s(s, "%d(%d)", &a, &b)==1) {//可用sscanf，如果使用sscnaf_f，对于%c的输入需要在后面指定长度
if (a > 0) {
sdu[k].num++;
sdu[k].time += a;
}
}
else {
sdu[k].num++; sdu[k].time += a + b*m;
}
}
k++;
}
输出
输出也有些麻烦，可以用sort排序
sort(sdu, sdu + k, cmp);
bool cmp(struct S a, struct S b)
{
if (a.num != b.num)
return a.num > b.num;
else
{
if (a.time != b.time)
return a.time < b.time;
else
return a.name < b.name;
}
}
最后按照格式输出排名
cout << setiosflags(ios::left) << setw(10) << sdu[i].name << " ";
cout << setiosflags(ios::right) << setw(2) << sdu[i].num << " ";
cout << setiosflags(ios::right) << setw(4) << sdu[i].time << endl;
5.瑞神HRZ因为疫情在家闲得无聊，同时他又非常厉害，所有的课对他来说都是水一水就能拿A+，所以他无聊，找来了另外三个人：咕咕东，腾神以及zjm来打牌（天下苦瑞神久矣）。
显然，牌局由四个人构成，围成一圈。我们称四个方向为北 东 南 西。对应的英文是North，East，South，West。游戏一共由一副扑克，也就是52张构成。开始，我们指定一位发牌员（东南西北中的一个，用英文首字母标识）开始发牌，发牌顺序为顺时针，发牌员第一个不发自己，而是发他的下一个人（顺时针的下一个人）。这样，每个人都会拿到13张牌。
现在我们定义牌的顺序，首先，花色是（梅花）<（方片）<（黑桃）<（红桃），（输入时，我们用C,D,S,H分别表示梅花，方片，黑桃，红桃，即其单词首字母）。对于牌面的值，我们规定2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < T < J < Q < K < A。
现在你作为上帝，你要从小到大排序每个人手中的牌，并按照给定格式输出。（具体格式见输出描述和样例输出）。
输入输出：输入包含多组数据
每组数据的第一行包含一个大写字符，表示发牌员是谁。如果该字符为‘#’则表示输入结束。
接下来有两行，每行有52个字符，表示了26张牌，两行加起来一共52张牌。每张牌都由两个字符组成，第一个字符表示花色，第二个字符表示数值。
输出多组数据发牌的结果，每组数据之后需要额外多输出一个空行！！！！！
每组数据应该由24行的组成，输出按照顺时针方向，始终先输出South Player的结果，每位玩家先输出一行即玩家名称（东南西北），接下来五行，第一行和第五行输出固定格式（见样例），第二行和第四行按顺序和格式输出数值（见样例），第三行按顺序和格式输出花色（见样例）。
分析
这道题本身不难，就是代码比较复杂不好整理
首先解决排序的问题，使用sort排序最简单。但是cmp不好编写，因为规定的2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < T < J < Q < K < A，实际中是 A <J<K<Q<T。所以我们可以使用map字典的方法，将字符映射为2到14的数字。这样的话，可以定义一个包含花色，字符和大小的结构体。
map m2;
m2['2']=2,m2['3']=3,m2['4']=4,m2['5']=5,
m2['6']=6,m2['7']=7,m2['8']=8,m2['9']=9,
m2['T']=10,m2['J']=11,m2['Q']=12,m2['K']=13,
m2['A']=14;
struct carts{
int num;
char cnum;
char col;
}cart[4][13];
bool cmp(carts a,carts b){
if(a.col==b.col){
return a.numb.col;
else return a.col<b.col;
}
else return a.col<b.col;
}
}
输入：每四个交替发给四个人，可以映射到二维数组中
其中，在定义一个map，把方向S、N、E、W映射到1到3数字中
for(int j=0;j>cart[i][j].col>>cart[i][j].cnum;
cart[i][j].num=m2[cart[i][j].cnum];
i=(i+1)%4;
}while(i!=k);
}
输出
按照格式输出
for(int i=0;i<4;i++){
if(i==0)cout<<"South player:";if(i==1)cout<<"West player:";if(i==2)cout<<"North player:";if(i==3)cout<<"East player:";
cout<<endl;
cout<<"+---+---+---+---+---+---+---+---+---+---+---+---+---+"<<endl;
for(int j=0;j<13;j++)cout<<"|"<<cart[i][j].cnum<<" "<<cart[i][j].cnum;
cout<<"|"<<endl;
for(int j=0;j<13;j++)cout<<"| "<<cart[i][j].col<<" ";
cout<<"|"<<endl;
for(int j=0;j<13;j++)cout<<"|"<<cart[i][j].cnum<<" "<<cart[i][j].cnum;
cout<<"|"<<endl;
cout<<"+---+---+---+---+---+---+---+---+---+---+---+---+---+"<<endl;
}
总结
本次作业（包括实验），回顾了bfs的用法，掌握了几种把“非坐标”题转化为“坐标”题的方法。
sscanf在特殊情况的用法，以及sscanf返回参数的巧妙利用。
作者：薛定谔捡的猫
