学习总结2

解题思路

用bfs进行搜索,标记A罐B罐所保存的水的出现情况,当再次出现的时候停止搜索,然后用数组模拟链表进行保存路径.最后输出.

代码

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
using namespace std;
int g[120][120];
struct s
{int x;int y;
}d[120*120];
int l,r;
struct ss
{int x;int y;int z;
}j[120][120];
int a,b,c;
int k,i;
int bfs()
{int tx,ty,z;while(l<r){for(z=0;z<6;z++){tx=d[l].x;ty=d[l].y;switch(z){case 0:tx=a;break;case 1:ty=b;break;case 2:tx=0;break;case 3:ty=0;break;case 4:if(tx!=0){if(tx+ty<=b){ty=tx+ty;tx=0;}else{tx=tx-(b-ty);ty=b;}}break;case 5:if(ty!=0){if(tx+ty<=a){tx=ty+tx;ty=0;}else{ty=ty-(a-tx);tx=a;}}break;}if(tx>a||ty>b||tx<0||ty<0)continue;if(tx==c||ty==c){k=tx;i=ty;j[k][i].x=d[l].x;j[k][i].y=d[l].y;j[k][i].z=z;g[tx][ty]=g[d[l].x][d[l].y]+1;return 0;}if(g[tx][ty]==-1){g[tx][ty]=g[d[l].x][d[l].y]+1;d[r].x=tx;d[r++].y=ty;j[tx][ty].x=d[l].x;j[tx][ty].y=d[l].y;j[tx][ty].z=z;}}l++;}return 0;
}void print(int x,int y)
{if(x==0&&y==0)return ;print(j[x][y].x,j[x][y].y);switch(j[x][y].z){case 0:printf("FILL(1)\n");break;case 1:printf("FILL(2)\n");break;case 2:printf("DROP(1)\n");break;case 3:printf("DROP(2)\n");break;case 4:printf("POUR(1,2)\n");break;case 5:printf("POUR(2,1)\n");break;}return ;
}int main()
{scanf("%d%d%d",&a,&b,&c);d[r].x=0;d[r++].y=0;memset(g,-1,sizeof(int )*120*120);g[0][0]=0;bfs();if(k==0&&i==0){printf("impossible\n");}else{printf("%d\n",g[k][i]);print(k,i);}return 0;
}

解题思路

这道题用bfs就行了.以两个人为起点对全图进行搜索,用一个数组保存到每一个地方所用的最短的步数.最后比较两人到所有的kfc所用的步数的总和输出最小的就行了.

代码

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
using namespace std;
char g[210][210];
int j[210][210];
int j2[210][210];
int ne[5][2]={{1,0},{-1,0},{0,1},{0,-1}};
int n,m;
struct di
{int x;int y;
}sy,sm,kfc[210*210],dl[210*210];
int l,r;
int k;
int sum;int bfs()
{int tx,ty,z;while(l<r){for(z=0;z<4;z++){tx=ne[z][0]+dl[l].x;ty=ne[z][1]+dl[l].y;if(tx<0||tx>n||ty<0||ty>m)continue;if(g[tx][ty]!='#'&&j[tx][ty]==0){j[tx][ty]=j[dl[l].x][dl[l].y]+1;dl[r].x=tx;dl[r++].y=ty;}}l++;}return 0;
}int bfs2()
{int tx,ty,z;while(l<r){for(z=0;z<4;z++){tx=ne[z][0]+dl[l].x;ty=ne[z][1]+dl[l].y;if(tx<0||tx>n||ty<0||ty>m)continue;if(g[tx][ty]!='#'&&j2[tx][ty]==0){j2[tx][ty]=j2[dl[l].x][dl[l].y]+1;dl[r].x=tx;dl[r++].y=ty;}}l++;}return 0;
}int main()
{int x,y,s;while(~scanf("%d%d",&n,&m)){sum=9999999;k=0;for(x=0;x<n;x++){scanf("%s",g[x]);}for(x=0;x<n;x++){for(y=0;y<m;y++){if(g[x][y]=='Y'){sy.x=x;sy.y=y;}if(g[x][y]=='M'){sm.x=x;sm.y=y;}if(g[x][y]=='@'){kfc[k].x=x;kfc[k++].y=y;}}}memset(j,0,sizeof(int)*210*210);l=0;r=0;dl[r].x=sy.x;dl[r++].y=sy.y;bfs();memset(j2,0,sizeof(int)*210*210);l=0;r=0;dl[r].x=sm.x;dl[r++].y=sm.y;bfs2();for(x=0;x<k;x++){if(j[kfc[x].x][kfc[x].y]!=0&&j2[kfc[x].x][kfc[x].y]!=0)if((j[kfc[x].x][kfc[x].y]+j2[kfc[x].x][kfc[x].y])<sum)sum=j[kfc[x].x][kfc[x].y]+j2[kfc[x].x][kfc[x].y];}printf("%d\n",sum*11);}return 0;
}

解题思路

用bfs搜索,要注意的是地图是三维的,传送到下一层之后可能的情况(直接见到公主,撞死,进入另一个传送门).

代码

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
using namespace std;
char g[3][15][15];
int j[3][15][15];
struct ss
{int x;int y;int z;
}d[15*15*3];
int ne[5][2]={{1,0},{-1,0},{0,1},{0,-1}};
int l,r;
int n,m,t;
int bfs()
{int z,tx,ty,tz;while(l<r){for(int z=0;z<4;z++){tx=d[l].x+ne[z][0];ty=d[l].y+ne[z][1];tz=d[l].z;if(tx<0||ty<0||tx>=n||ty>=m)continue;if(g[tz][tx][ty]=='P'){return j[tz][tx][ty]=j[d[l].z][d[l].x][d[l].y]+1;}if(g[tz][tx][ty]!='*'&&j[tz][tx][ty]==-1){j[tz][tx][ty]=j[d[l].z][d[l].x][d[l].y]+1;if(g[tz][tx][ty]=='#'){if(tz==0){tz++;}else{tz--;}if(g[tz][tx][ty]=='#'||j[tz][tx][ty]!=-1){if(tz==0){tz++;}else{tz--;}continue;}if(g[tz][tx][ty]=='*'||j[tz][tx][ty]!=-1){if(tz==0){tz++;}else{tz--;}continue;}if(g[tz][tx][ty]=='P'){return j[tz][tx][ty]=j[d[l].z][d[l].x][d[l].y]+1;}j[tz][tx][ty]=j[d[l].z][d[l].x][d[l].y]+1;}d[r].x=tx;d[r].y=ty;d[r++].z=tz;}}l++;}return 999999;
}
int main()
{int k;scanf("%d",&k);for(int z=0;z<k;z++){memset(j,-1,sizeof(int )*3*15*15);l=r=0;scanf("%d%d%d",&n,&m,&t);for(int x=0;x<n;x++){scanf("%s",g[0][x]);}getchar();for(int x=0;x<n;x++){scanf("%s",g[1][x]);}d[r].x=0;d[r].y=0;d[r++].z=0;j[0][0][0]=0;int sum=bfs();if(sum<=t){printf("YES\n");}else{printf("NO\n");}}return 0;
}