注意此处提供了链接
8. 罐子
问题描述
给你两个罐子，容积分别为 $A$ 升和 $B$ 升。
现在，你可以进行如下三种操作：
FILL(i)，将罐子$i$（$1\leqslant i \leqslant 2$）灌满水。DROP(i)，将罐子 $i$（$1\leqslant i \leqslant 2$）清空。POUR(i,j)，将罐子 $i$ 中的水倒向罐子 $j$，直到罐子 $i$ 空了或罐子 $j$ 满了为止。
请问，至少多少次操作后，可以使得其中一个罐子里恰好有 $C$ 升水。输入格式
共一行，三个整数 $A,B,C$。
输出格式
如果无解，则输出一行
impossible即可。
否则，第一行输出一个整数，表示最少操作次数。
随后按顺序每行输出一个操作指令，格式参考题面。数据范围
$1\leqslant A,B,C \leqslant 100$,
$C \leqslant max(A,B)$。输入样例
$3$ $5$ $4$
输出样例
$6$
FILL(2)
POUR(2,1)
DROP(1)
POUR(2,1)
FILL(2)
POUR(2,1)
思路
基于bfs的思想,将两个杯子分别看作坐标系中的$x$和$y$,去跑bfs即可,此时无非就6种情况,倒满$A$(来源于$B$或外界倒满),倒空$A$,倒满$B$(来源于$A$或外界倒满),倒空$B$.
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define MAXN 110
using namespace std;
int A,B,C;
struct node{
int x;
int y;
int step;
string op;
};
string res[6]={"FILL(1)", "FILL(2)", "DROP(1)","DROP(2)","POUR(1,2)","POUR(2,1)"};
int vis[MAXN][MAXN];
void bfs()
{
queue<node> q;
q.push({0,0,0,""});
vis[0][0]=1;
while(q.size()>0)
{
node temp=q.front();
q.pop();
if(temp.x==C||temp.y==C)
{
//cout << temp.op << "***" << endl;
cout << temp.step << endl;
for(int i=0;i<temp.step;i++)
cout << res[temp.op[i]] << endl;
return ;
}
int temp1=min(temp.x,B-temp.y);
int temp2=min(temp.y,A-temp.x);
//倒满,倒空,A->B,B->A
int dir[6][2]={{A-temp.x,0},{0,B-temp.y},{-temp.x,0},{0,-temp.y},{-temp1,temp1},{temp2,-temp2}};
for(int i=0;i<=5;i++)
{
int dx=temp.x+dir[i][0],dy=temp.y+dir[i][1];
if(vis[dx][dy]==0)
{
char temp_op=i;
string s=temp.op+temp_op;
q.push({dx,dy,temp.step+1,s});
vis[dx][dy]=1;
}
}
}
printf("impossible\n");
}
int main()
{
scanf("%d %d %d",&A,&B,&C);
bfs();
return 0;
}
9. 点火游戏
问题描述
给定一个 $N$ 行 $M$ 列的方格矩阵。
其中一部分方格是草地，其余部分是空地。
草地能够被燃烧，空地不会。
当某个草地在 $t$ 时刻被点燃时，其上下左右四个方向的相邻方格中的草地方格也会在 $t+1$ 时刻被点燃。
注意，空地方格无论如何都不可能被点燃。
现在，你可以选择最多两个草地，将它们点燃。
请你计算，使得所有草地都被点燃所需花费的最少时间。输入格式
第一行包含整数 $T$，表示共有 $T$ 组测试数据。
每组数据第一行包含两个整数 $N,M$。
接下来 $N$ 行，包含一个 $N \times M$ 的字符矩阵，#表示草地，.表示空地。输出格式
每组数据输出一个结果，每个结果占一行。
结果表示为Case x: y，其中 $x$ 为组别编号（从 $1$ 开始），$y$ 点燃所有草地需要花费的最短时间。如果无法点燃所有草地或者所有方格都是空地则输出 $-1$。数据范围
$1 \leqslant T \leqslant 100$,
$1 \leqslant N,M \leqslant 10$。输入样例
$5$
$3$ $3$
.#.
###
.#.
$3$ $3$
.#.
#.#
.#.
$3$ $3$
…
#.#
…
$3$ $3$
###
..#
#.#
$3$ $3$
…
…
…输出样例
Case $1$: $1$
Case $2$: $-1$
Case $3$: $0$
Case $4$: $2$
Case $5$: $-1$
思路
经典的bfs问题,此题可暴力枚举两个草地的情况(可能存在一个草堆的情况,在跑两重循环第二层应从$i$开始),无终止条件,在$bfs$跑完后判断当前燃烧的草堆的个数是否与所有的草堆个数相等,返回最长的时间,并每次取最小值.
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstdio>
#define MAXN 15
using namespace std;
typedef pair<int,int> PII;
const int inf=0x3f3f3f3f;
int t,n,m,res,sum,vis[MAXN][MAXN];
char g[MAXN][MAXN];
struct node{
int x;
int y;
int step;
};
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
int bfs(PII a,PII b)
{
queue<node> q;
memset(vis,0,sizeof(vis));
q.push({a.first,a.second,0});
if(a!=b)
q.push({b.first,b.second,0});
vis[a.first][a.second]=vis[b.first][b.second]=1;
int cnt=0,maxx=0;
while(q.size()>0)
{
node temp=q.front();
q.pop();
cnt++;
for(int i=0;i<=3;i++)
{
int dx=temp.x+dir[i][0],dy=temp.y+dir[i][1];
if(dx>=1&&dx<=n&&dy>=1&&dy<=m&&vis[dx][dy]==0&&g[dx][dy]=='#')
{
maxx=max(maxx,temp.step+1);
vis[dx][dy]=1;
q.push({dx,dy,temp.step+1});
}
}
}
if(cnt==sum)
return maxx;
return -1;
}
int main()
{
scanf("%d",&t);
int cas=1;
while(t--)
{
vector<PII> v;
res=inf;
sum=0;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%s",g[i]+1);
for(int j=1;j<=m;j++)
if(g[i][j]=='#')
v.push_back({i,j}),sum++;
}
for(int i=0;i<sum;i++)
for(int j=i;j<sum;j++)//注意此处是i,不是i+1,它有可能只有一堆
{
int temp=bfs(v[i],v[j]);
if(temp!=-1)
res=min(res,temp);
}
if(res==inf)
printf("Case %d: -1\n",cas++);
else printf("Case %d: %d\n",cas++,res);
}
return 0;
}
10. 起火迷宫
问题描述
一个迷宫可以看作一个 $R$ 行 $C$ 列的方格矩阵。
其中一些方格是空地，用.表示，其他方格是障碍，用#表示。
开始时，乔位于一块空地之中。
迷宫中一些空地已经起火了，幸运的是火还没有蔓延至乔所在的位置。
为了避免被火烧伤，乔需要尽快逃离迷宫。
已知，乔每单位时间只能沿上下左右四个方向前进一格距离，并且在前进过程中，他不能进入障碍方格。
火每单位时间都会蔓延至其上下左右四个方向的相邻空地，但是火也会被障碍阻挡。
如果一个方格已经起火或者会在乔进入方格的那一时刻恰好起火，则该方格很危险，乔不能进入。
当乔进入到任意一个位于边界的空地方格时，他都可以再花费一单位时间，直接逃离迷宫。
请问，乔想要逃离迷宫，最少需要花费的时间。输入格式
第一行包含整数 $T$，表示共有 $T$ 组测试数据。
每组数据第一行包含两个整数 $R,C$。
接下来 $R$ 行，包含一个 $R \times C$ 的字符矩阵。
矩阵中只包含以下四种字符：
#表示障碍方格。.表示空地方格。J表示乔所在的空地方格，最多只有一个。F表示已经起火的空地方格。输出格式
每组数据输出一行结果，一个整数表示逃离迷宫所需花费的最少时间，如果无法逃离迷宫，则输出
IMPOSSIBLE。数据范围
$1 \leqslant T \leqslant 10$,
$1 \leqslant R,C \leqslant 1000$。输入样例
$2$
$4$ $4$
####
#JF#
#..#
#..#
$3$ $3$
###
#J.
#.F输出样例
$3$
IMPOSSIBLE
思路
基于bfs思想,先把火的蔓延情况跑一遍$bfs$,然后把人(注意考虑他到达边界的情况和他能走的情况必然在火蔓延之前,即$t_{人}+1 < t_{火}$)的行走情况跑一遍$bfs$.
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#define MAXN 1010
using namespace std;
const int inf=0x3f3f3f3f;
typedef pair<int, int> PII;
int dir[4][2]={{0,-1},{1,0},{0,1},{-1,0}};
int t,n,m,sx,sy;
char g[MAXN][MAXN];
int dist[MAXN][MAXN];//火
int Dist[MAXN][MAXN];//人
vector<PII> v;
void bfs()
{
queue<PII> q;
for(int i=0;i<v.size();i++)
{
q.push({v[i].first,v[i].second});
dist[v[i].first][v[i].second]=0;
}
while(q.size()>0)
{
PII temp=q.front();
q.pop();
for(int i=0;i<=3;i++)
{
int dx=temp.first+dir[i][0],dy=temp.second+dir[i][1];
if(dx>=1&&dx<=n&&dy>=1&&dy<=m&&dist[dx][dy]==inf&&g[dx][dy]=='.')
{
dist[dx][dy]=dist[temp.first][temp.second]+1;
q.push({dx,dy});
}
}
}
}
int BFS()
{
if(sx==1||sx==n||sy==1||sy==m)
return 1;
queue<PII> q;
q.push({sx,sy});
Dist[sx][sy]=0;
while(q.size()>0)
{
PII temp=q.front();
q.pop();
if(temp.first==1||temp.first==n||temp.second==1||temp.second==m)
return Dist[temp.first][temp.second]+1;
for(int i=0;i<=3;i++)
{
int dx=temp.first+dir[i][0],dy=temp.second+dir[i][1];
if(dx>=1&&dx<=n&&dy>=1&&dy<=m&&Dist[dx][dy]==inf&&g[dx][dy]=='.'&&Dist[temp.first][temp.second]+1<dist[dx][dy])
{
Dist[dx][dy]=Dist[temp.first][temp.second]+1;
q.push({dx,dy});
}
}
}
return 0;
}
int main()
{
cin >> t;
while(t--)
{
memset(dist,0x3f,sizeof(dist));
memset(Dist,0x3f,sizeof(Dist));
v.clear();
cin >> n >> m;
for(int i=1;i<=n;i++)
{
cin >> g[i]+1;
for(int j=1;j<=m;j++)
{
if(g[i][j]=='J')
sx=i,sy=j;
else if(g[i][j]=='F')
v.push_back({i,j});
}
}
bfs();//火
int res=BFS();
if(res!=0)
cout << res << endl;
else cout << "IMPOSSIBLE" << endl;
}
return 0;
}
11. 迷宫问题
问题描述
给定一个 $n \times n$ 的二维数组，如下所示：
int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 0, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
它表示一个迷宫，其中的$1$表示墙壁，$0$表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
数据保证至少存在一条从左上角走到右下角的路径。输入格式
第一行包含整数 $n$。
接下来 $n$ 行，每行包含 $n$ 个整数 $0$ 或 $1$，表示迷宫。输出格式
输出从左上角到右下角的最短路线，如果答案不唯一，输出任意一条路径均可。
按顺序，每行输出一个路径中经过的单元格的坐标，左上角坐标为 $(0,0)$，右下角坐标为 $(n-1,n-1)$。数据范围
$0 \leqslant n \leqslant 1000$
输入样例
$5$
$0$ $1$ $0$ $0$ $0$
$0$ $1$ $0$ $1$ $0$
$0$ $0$ $0$ $0$ $0$
$0$ $1$ $1$ $1$ $0$
$0$ $0$ $0$ $1$ $0$输出样例
$0$ $0$
$1$ $0$
$2$ $0$
$2$ $1$
$2$ $2$
$2$ $3$
$2$ $4$
$3$ $4$
$4$ $4$
思路
基于bfs的思想,这题主要考察的是输出路径,可采取递归实现路径的输出,用$xx$数组记录当前点的前驱结点的横坐标,用$yy$数组记录当前点的前驱结点的纵坐标,此题我下标是从(1,1)开始的,输出时坐标应为$(x-1,y-1)$.
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cstdio>
#define MAXN 1010
using namespace std;
int n;
int g[MAXN][MAXN];
int xx[MAXN][MAXN],yy[MAXN][MAXN];
int vis[MAXN][MAXN];
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
struct node{
int x;
int y;
int step;
};
int bfs()
{
queue<node> q;
q.push({1,1,0});
vis[1][1]=1;
while(q.size()>0)
{
node temp=q.front();
q.pop();
if(temp.x==n&&temp.y==n)
return temp.step;
for(int i=0;i<=3;i++)
{
int dx=temp.x+dir[i][0],dy=temp.y+dir[i][1];
if(dx>=1&&dx<=n&&dy>=1&&dy<=n&&vis[dx][dy]==0&&g[dx][dy]==0)
{
//cout << dx << " " << dy << endl;
vis[dx][dy]=1;
q.push({dx,dy,temp.step+1});
xx[dx][dy]=temp.x;
yy[dx][dy]=temp.y;
}
}
}
return -1;
}
void pre_out(int x,int y)
{
if(x!=1||y!=1)
{
pre_out(xx[x][y],yy[x][y]);
printf("%d %d\n",x-1,y-1);
return ;
}
printf("0 0\n");
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&g[i][j]);
int res=bfs();
//cout << res << endl;
pre_out(n,n);
return 0;
}
12. 石油储备
问题描述
一片土地可以看作是一个 $n$ 行 $m$ 列的方格矩阵。
其中一些方格藏有石油，用@表示，其余方格没有石油，用*表示。
每个方格都与其上、下、左、右、左上、右上、左下、右下八个方格视为相邻。
如果两个藏有石油的方格相邻，则它们被认为是处于同一片油田，否则它们被认为是处于不同油田。
请问，该土地中共有多少片油田。输入格式
输入包含多组测试数据。
每组数据第一行包含两个整数 $n,m$。
接下来 $n$ 行，包含一个 $n$ 行 $m$ 列的字符矩阵，表示土地情况。
当输入一行0 0时，表示输入结束。输出格式
每组数据输出一行，一个整数，表示油田数量。
数据范围
最多包含 $100$ 组数据。
$1 \leqslant n,m \leqslant 100$。输入样例
$1$ $1$
*
$3$ $5$
*@*@*
**@**
*@*@*
$1$ $8$
@@****@*
$5$ $5$
****@
*@@*@
*@**@
@@@*@
@@**@
$0$ $0$输出样例
$0$
$1$
$2$
$2$
思路
基于bfs的思想,一次枚举没有标记的石油方格,枚举的次数即为答案.
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cstdio>
#define MAXN 110
using namespace std;
int n,m,cnt;
char g[MAXN][MAXN];
int vis[MAXN][MAXN];
struct node{
int x;
int y;
};
int dir[8][2]={{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
void bfs(int x,int y)
{
queue<node> q;
q.push({x,y});
vis[x][y]=1;
while(q.size()>0)
{
node temp=q.front();
q.pop();
for(int i=0;i<=7;i++)
{
int dx=temp.x+dir[i][0],dy=temp.y+dir[i][1];
if(dx>=1&&dx<=n&&dy>=1&&dy<=m&&vis[dx][dy]==0&&g[dx][dy]=='@')
{
q.push({dx,dy});
vis[dx][dy]=1;
}
}
}
}
int main()
{
while(scanf("%d %d",&n,&m)!=EOF)
{
if(n==0&&m==0)
break;
memset(vis,0,sizeof(vis));
cnt=0;
for(int i=1;i<=n;i++)
scanf("%s",g[i]+1);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(g[i][j]=='@'&&vis[i][j]==0)
bfs(i,j),cnt++;
printf("%d\n",cnt);
}
return 0;
}
13. 非常可乐
问题描述
大家一定觉的运动以后喝可乐是一件很惬意的事情，但是 $seeyou$ 却不这么认为。
因为每次当 $seeyou$ 买了可乐以后，阿牛就要求和 $seeyou$ 一起分享这一瓶可乐，而且一定要喝的和 $seeyou$ 一样多。
但 $seeyou$ 的手中只有两个杯子，它们的容量分别是 $N$ 毫升和 $M$ 毫升。
可乐的体积为 $S$ （$S<101$）毫升 (正好装满一瓶) ，它们三个之间可以相互倒可乐 (都是没有刻度的，且 $S=N+M,101＞S＞0，N＞0，M＞0$) 。
聪明的 $ACMER$ 你们说他们能平分吗？
如果能请输出倒可乐的最少的次数，如果不能输出NO。输入格式
输入包含多组测试数据。
每组数据一行，三个整数 $S,N,M$。
当输入一行为0 0 0时，表示输入结束。输出格式
每组数据输出一行结果，如果能够平分，则输出倒可乐的最少的次数，否则输出
NO。数据范围
$S=N+M，101＞S＞0，N＞0，M＞0$
输入样例
$7$ $4$ $3$
$4$ $1$ $3$
$0$ $0$ $0$输出样例
NO
$3$
思路
与罐子那题类似,无非就多一维的bfs,注意从$i$倒入$j$,倒入的容积是$min(w[i],v[j]-w[j])$.
另给一种大佬的数论做法巨佬链接
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cstdio>
#define MAXN 110
using namespace std;
int val[3];
int vis[MAXN][MAXN][MAXN];
struct node{
int w[3];
int step;
};
int bfs()
{
memset(vis,0,sizeof(vis));
queue<node> q;
q.push({val[0],0,0,0});
vis[val[0]][0][0]=1;
while(q.size()>0)
{
node temp=q.front();
q.pop();
if(temp.w[0]==temp.w[2]&&temp.w[1]==0)
return temp.step;
for(int i=0;i<=2;i++)
for(int j=0;j<=2;j++)
{
if(i!=j)
{
node tempp=temp;
int minx=min(tempp.w[i],val[j]-tempp.w[j]);//从i->j倒
tempp.w[i]-=minx,tempp.w[j]+=minx;
if(vis[tempp.w[0]][tempp.w[1]][tempp.w[2]]==0)
{
//cout << tempp.w[0] << " " << tempp.w[1] << " " << tempp.w[2] << endl;
tempp.step++;
q.push(tempp);
vis[tempp.w[0]][tempp.w[1]][tempp.w[2]]=1;
}
}
}
}
return -1;
}
int main()
{
while(scanf("%d %d %d",&val[0],&val[1],&val[2])!=EOF)
{
if(val[0]==0&&val[1]==0&&val[2]==0)
break;
if(val[0]%2==1)
printf("NO\n");
else
{
if(val[1]>val[2])
swap(val[1],val[2]);
int res=bfs();
if(res==-1)
printf("NO\n");
else printf("%d\n",res);
}
}
return 0;
}
14. 找路
问题描述
给定一个 $n$ 行 $m$ 列的方格矩阵。
其中有些方格是空地（可以进入），有些方格是餐厅（可以进入），有些方格是障碍（不可进入）。
开始时，小 $Y$ 和小 $M$ 各自位于一个空地方格中。
每个人都可以沿上下左右四个方向进行移动，移动一格距离需要花费 $11$ 分钟时间。
他们希望选择一家餐厅进行聚餐，要求两人从各自出发点到达该餐厅所花费的时间之和尽可能小。
输出这个最小时间和。输入格式
输入包含多组测试数据。
每组数据第一行包含两个整数 $n,m$。
接下来 $n$ 行，包含一个 $n×m$ 的字符矩阵。
矩阵中只包含以下五种字符：
#表示障碍方格。.表示空地方格。Y表示小 $Y$ 所在的空地方格，有且仅有一个。M表示小 $M$ 所在的空地方格，有且仅有一个。@表示餐厅。输出格式
每组数据输出一行答案，表示最小时间和。
保证一定有解。数据范围
最多包含 $100$ 组数据。
$2 \leqslant n,m \leqslant 200$。输入样例
$4$ $4$
Y.#@
….
.#..
@..M
$4$ $4$
Y.#@
….
.#..
@#.M
$5$ $5$
Y..@.
.#…
.#…
@..M.
#…#输出样例
$66$
$88$
$66$
思路
分别跑两个人的$bfs$,用$dist1$数组存储第一个人的行走情况,用$dist2$数组存储第二个人的行走情况,最后枚举所有的餐馆取$11 \times (dist1+dist2)$最小值即可.
代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <vector>
#define MAXN 210
using namespace std;
const int inf=0x3f3f3f3f;
int n,m;
struct node{
int x;
int y;
};
int sx1,sy1,sx2,sy2;
char g[MAXN][MAXN];
int dist1[MAXN][MAXN],dist2[MAXN][MAXN],dist[MAXN][MAXN];
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
void bfs(int sx,int sy)
{
//memset(dist,0x3f,sizeof(dist));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
dist[i][j]=inf;
queue<node> q;
q.push({sx,sy});
dist[sx][sy]=0;
while(q.size()>0)
{
node temp=q.front();
q.pop();
for(int i=0;i<=3;i++)
{
int dx=temp.x+dir[i][0],dy=temp.y+dir[i][1];
if(dx>=1&&dx<=n&&dy>=1&&dy<=m&&dist[dx][dy]==inf&&g[dx][dy]!='#')
{
q.push({dx,dy});
dist[dx][dy]=dist[temp.x][temp.y]+1;
}
}
}
}
int main()
{
while(scanf("%d %d",&n,&m)!=EOF)
{
vector<node> v;
for(int i=1;i<=n;i++)
{
scanf("%s",g[i]+1);
for(int j=1;j<=m;j++)
{
if(g[i][j]=='Y')
sx1=i,sy1=j;
else if(g[i][j]=='M')
sx2=i,sy2=j;
else if(g[i][j]=='@')
v.push_back({i,j});
}
}
bfs(sx1,sy1);
//memcpy(dist1,dist,sizeof(dist));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
dist1[i][j]=dist[i][j];
bfs(sx2,sy2);
//memcpy(dist2,dist,sizeof(dist));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
dist2[i][j]=dist[i][j];
int res=inf;
for(int i=0;i<v.size();i++)
res=min(res,11*(dist1[v[i].x][v[i].y]+dist2[v[i].x][v[i].y]));
printf("%d\n",res);
}
return 0;
}
