【USACO-水桶传递队列】三种角度深刻理解

问题描述

农场上起火了，奶牛们正在紧急赶去灭火！农场可以用一个像这样的 10×10 的字符方阵来描述：................................B......................R.............................L..............字符’B’表示正着火的牛棚，字符’L’表示一个湖，而字符’R’表示农场上的一块巨大岩石。奶牛们想要沿着一条湖到牛棚之间的路径组成一条“水桶传递队列”，这样她们就可以沿着这条路径传递水桶来帮助灭火。当两头奶牛在东南西北四个方向上相邻时水桶可以在她们之间传递。湖边的奶牛也是如此——奶牛只能在紧挨着湖的时候才能用水桶从湖里取水。类似地，奶牛只能在紧挨着牛棚的时候才能用水去灭牛棚的火。请帮助求出奶牛们为了组成这样的“水桶传递队列”需要占据的’.’格子的最小数量。奶牛不能站在岩石所在的方格之内，此外保证牛棚和湖不是相邻的。输入格式输入包含 10 行，每行 10 个字符，描述这个农场的布局。输入保证图案中恰有一个字符’B’、一个字符’L’以及一个字符’R’。输出格式输出一个整数，为组成一条可行的水桶传递队列所需要的奶牛的最小数量。输入样例：................................B......................R.............................L..............输出样例：7样例解释在这个例子中，以下是一个可行的方案，使用了最小数量的奶牛（7）：................................B.........C.........CC.R.......CCC.........C.........L..............

思路分析

一看好像是道经典的搜索题目。大概率要用bfs，我在最开始尝试了一下dfs，不过一直爆栈或者tle。最后根据找到的性质进行了剪枝。后面又尝试了下bfs。最后发现其实也可以是分类讨论

一、DFS

#include using namespace std;char g[20][20];bool b[20][20];int ne[5][3]= {{0,1},{1,0},{0,-1},{-1,0}};/偏移量int sx,sy;//牛棚的位置int ex,ey;//湖的位置int tx,ty;//石子的位置int t;//标记三者是否在同一条直线上int res=1e8;void dfs(int x,int y,int step){    if(step>abs(ey-sy)+abs(ex-sx)+t)//剪枝 return;    if(x==ex&&y==ey)//如果到了终点，更新    { res=min(step,res); return;    }    for(int k=0; k=0&&t1=0&&t2<10&&g[t1][t2]!='R'&&!b[t1][t2]) {     b[t1][t2]=1;     dfs(t1,t2,step+1);     b[t1][t2]=0; }    }}int main(){    for(int i=0; i<10; i++) for(int j=0; j>g[i][j];     if(g[i][j]=='B')  sx=i,sy=j;     if(g[i][j]=='L')  ex=i,ey=j;     if(g[i][j]=='R')  tx=i,ty=j; }    if(ty==sy&&ty==ey||tx==sx&&tx==ex)//特判一下是不是三者在一条直线上 t=2;    b[sx][sy]=1;    dfs(sx,sy,0);    cout<<res-1;//减1是因为把终点也算了进去    return 0;}

二、BFS

#include #include #include #include #include using namespace std;typedef pair PII;char g[20][20];int d[20][20];bool st[20][20];int ne[5][3]={{0,1},{1,0},{0,-1},{-1,0}};int n=10,m=10;int x1,y1,x2,y2;int bfs(){    queue q;    q.push({x1,y1});    memset(d,-1,sizeof d);    d[x1][y1]=0;    while(q.size())    { auto t=q.front(); q.pop(); for(int k=0;k=0&&x=0&&y<m&&d[x][y]==-1&&!st[x][y]&&g[x][y]!='R')     {  q.push({x,y});  d[x][y]=d[t.first][t.second]+1;     } }    }    return d[x2][y2];}int main(){    for(int i=0;i<n;i++) for(int j=0;j>g[i][j];     if(g[i][j]=='L')  x2=i,y2=j;     else if(g[i][j]=='B')  x1=i,y1=j; }    st[x1][y1]=true;    cout<<bfs()-1;    return 0;}

三、分类讨论

#include //分类讨论using namespace std;int main(){    int x1,y1,x2,y2,x3,y3;    for(int i=0;i<10;i++)    { for(int j=0;j>x;     if(x=='B') x1=i,y1=j;     else if(x=='R') x2=i,y2=j;     else if(x=='L') x3=i,y3=j; }    }    int res=abs(x3-x1)+abs(y3-y1);    if(x1==x2&&x2==x3&&(y2-y1)*(y2-y3)<0||y1==y2&&y1==y3&&(x2-x1)*(x2-x3)<0) res+=2;    cout<<res-1;    return 0;}