【POJ3126 Prime Path】【POJ 3087 Shuffle'm Up】【UVA 11624 Fire!】【POJ 3984 迷宫问题】

POJ3126Prime Path
给定两个四位素数a  b，要求把a变换到b
变换的过程要 每次变换出来的数都是一个 四位素数，而且当前这步的变换所得的素数  与  前一步得到的素数  只能有一个位不同，而且每步得到的素数都不能重复。
 

///果不其然各种姿势操T了,在暴力的时候，调用了太多的C++库文件 #include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <sstream> #include <queue> using namespace std; const int maxn=2e5; bool a[maxn]; bool prime[maxn]; bool vis[maxn]; int step[maxn]; string n,m; int cnt=0;//四位数的素数也就有1061个 void getprime(){memset(a,false,sizeof(a));memset(prime,false,sizeof(prime));for(int i=2; i<10000; ++i){if(!a[i]){if(i>=1000)prime[i]=true;for(int j=i*i; j<10000; j+=i)a[j]=true;}} } void bfs(){memset(vis,false,sizeof(vis));string tmp;queue<string>q;q.push(m);int mm=atoi(m.c_str());vis[mm]=1;step[mm]=0;int k=0;while(!q.empty()){string p=q.front();q.pop();int pp=atoi(p.c_str());if(p==n){printf("%d\n",step[pp]);return ;}for(int i=0; i<=9; ++i){for( k=0; k<4; ++k){tmp.clear();for(int j=0; j<k; ++j) tmp+=p[j];stringstream ss; ss<<i; tmp+=ss.str();//tmp+=std::to_string(i);for(int j=k+1; j<4; ++j) tmp+=p[j];int tmpp=atoi(tmp.c_str());if(prime[tmpp]&&!vis[tmpp]){q.push(tmp);step[tmpp]=step[pp]+1;vis[tmpp]=true;}}}}printf("Impossible\n"); } int main(){getprime();int t;scanf("%d",&t);while(t--){cin>>m>>n;bfs();}return 0; } #include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <sstream> #include <queue> using namespace std; const int maxn=2e5; bool a[maxn]; bool prime[maxn]; bool vis[maxn]; int step[maxn]; int n,m; int cnt=0;//四位数的素数也就有1061个 void getprime(){memset(a,false,sizeof(a));memset(prime,false,sizeof(prime));for(int i=2; i<10000; ++i){if(!a[i]){if(i>=1000)prime[i]=true;for(int j=i*i; j<10000; j+=i)a[j]=true;}} } //将number的倒数第pos位置变为val int get(int num,int pos,int val){switch(pos){case 0:return num/10*10+val;case 1:return num/100*100+val*10+num%10;case 2:return num/1000*1000+val*100+num%100;case 3:return num%1000+val*1000;} } void bfs(){memset(vis,false,sizeof(vis));queue<int>q;q.push(m);vis[m]=1;step[m]=0;int k=0;while(!q.empty()){int p=q.front();q.pop();if(p==n){printf("%d\n",step[p]);return ;}for(int i=0; i<=9; ++i){for( k=0; k<4; ++k){if(k==3&&i==0) continue;int tmp=get(p,k,i);if(prime[tmp]&&!vis[tmp]){q.push(tmp);step[tmp]=step[p]+1;vis[tmp]=true;}}}}printf("Impossible\n"); } int main(){int t;getprime();scanf("%d",&t);while(t--){scanf("%d%d",&m,&n);bfs();}return 0; }

POJ 3087 Shuffle'm Up
已知两堆牌s1和s2的初始状态， 其牌数均为c，按给定规则能将他们相互交叉组合成一堆牌s12，再将s12的最底下的c块牌归为s1，最顶的c块牌归为s2，依此循环下去。
现在输入s1和s2的初始状态 以及 预想的最终状态s12
问s1 s2经过多少次洗牌之后，最终能达到状态s12，若永远不可能相同，则输出"-1"。

模拟：

#include <cstdio> #include <iostream> #include <queue> #include <map> #include <cstring> using namespace std; int main() {int t;scanf("%d",&t);for(int ca=1;ca<=t;++ca){int n;char s1[1005],s2[1005],en[10000];map<string,bool >m;scanf("%d",&n);scanf("%s",s1);scanf("%s",s2);scanf("%s",en);int step=0;int times=1000,ti=0;while(true){ti++;char s[1000];int pc=0;for(int i=0;i<n;++i){s[pc++]=s2[i];s[pc++]=s1[i];}s[pc]='\0';step++;if(!strcmp(s,en)){printf("%d %d\n",ca,step);break;}if(m[s]){printf("%d %d\n",ca,-1);break;}m[s]=true;strncpy(s1,s,n);s1[n]='\0';strncpy(s2,s+n,n);s2[n]='\0';if(ti==times){printf("%d %d\n",ca,-1);break;}}} return 0; }

dfs:

#include <cstdio> #include <iostream> #include <queue> #include <map> #include <cstring> using namespace std; int ans,n; map<string,int>m; char s1[200],s2[200],s3[200]; void dfs(char s[],int step){if((ans=-1&&step>=ans)||m[s])return;if(m[s])return;if(!strcmp(s,s3)){ans=step;return ;}m[s]=true;char ss[200]="";int op=0;for(int i=0;i<n;++i){ss[op++]=s[i+n];ss[op++]=s[i];}dfs(ss,step+1); } int main(){int t;char ss[200];scanf("%d",&t);for(int ca=1;ca<=t;++ca){ans=-1;m.clear();// map<>scanf("%d",&n);scanf("%s",s1);scanf("%s",s2);scanf("%s",ss);char s[200];int op=0;for(int i=0;i<n;++i){s[op++]=s1[i];s[op++]=s2[i];}dfs(s,1);printf("%d %d\n",ca,ans);} }

UVA 11624 Fire!
题意：帮助joe走出一个大火蔓延的迷宫，其中joe每分钟可往上下左右四个方向之一走，所有着火的格子都会蔓延（空格与着火格有公共边，下一分钟这个空格也会着火）。迷宫中有一些障碍格，joe和火都无法进入，当joe走到一个边界的格子我们认为他走出了迷宫
 输出R行C列的迷宫，#表示墙，.表示空地，J表示joe，F是着火格
 如果能走出，输出最少时间否则，impossible
感觉很经典的一个问题,在处理每个点着火的时间的时候，却发现假若当前这个点之前已经被火着过一次怎么办了，在一想这就是简单的bfs最优性质决定的，用宽搜的时候就已经保证了在搜索过的着火点已经是最优的了
 

#include <iostream> #include<cstdio> #include <iostream> #include <cstring> #include <queue> using namespace std; typedef long long ll; const int maxn=(int)1e3+10; char map[maxn][maxn]; int step[maxn][maxn]; int vis[maxn][maxn]; int n,m; ll inf=0x3f3f3f3f; int dir[4][2]={{1,0},{0,1},{0,-1},{-1,0}};queue<pair<int,int> >q;void clear(queue<pair<int,int> >& q){queue<pair<int,int> > empty;swap(empty,q);} void bfs_fire(){while(!q.empty()){pair<int,int> p=q.front();q.pop();int x=p.first,y=p.second;// vis[x][y]=1;//vis[p.first][p.second]=1; 如果一直用first second去查找肯定会耗费时间pair<int,int> tmp;for(int i=0;i<4;++i){int dx=x+dir[i][0];int dy=y+dir[i][1];if(dx<1||dx>n||dy<1||dy>m||step[dx][dy]!=inf)continue;if(map[dx][dy]=='#')continue;tmp.first=dx,tmp.second=dy;step[dx][dy]=step[x][y]+1;q.push(tmp);}} } int pe[maxn][maxn]; void bfs_person(){pair<int,int > p;while(!q.empty()){p=q.front();q.pop(); int x=p.first,y=p.second;if(x==1||x==n||y==1||y==m){printf("%d\n",pe[x][y]+1);return ;}// vis[x][y]=1;for(int i=0;i<4;++i){int dx=x+dir[i][0];int dy=y+dir[i][1];if(dx<1||dx>n||dy<1||dy>m||pe[dx][dy]!=inf)continue;if(map[dx][dy]=='#')continue;if( (pe[x][y]+1<step[dx][dy]) ){//&&step[dx][dy]!=inf wa //加上这个！=inf开始是为了防止更新到障碍物所在的方格，其实上面的！=#已经判断了，不加也可以，不过加上他之后竟然wa掉，那就是说存在数据火到不了的网格人可以到，障碍物把火源包围了的这种情况pe[dx][dy]=pe[x][y]+1;q.push(make_pair(dx,dy));}}}printf("IMPOSSIBLE\n");return ; } void solve(){memset(step,inf,sizeof(step));//memset(vis,0,sizeof(vis));while(!q.empty())q.pop();//clear(q);// for(int i=1;i<=n;++i){// for(int j=1;j<=m;++j)// cout<<map[i][j];// cout<<endl;// }for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){if(map[i][j]=='F'){step[i][j]=0;q.push(make_pair(i,j));}}bfs_fire();// for(int i=1;i<=n;++i){// for(int j=1;j<=m;++j){// cout<<step[i][j]<<' ';// }// cout<<endl;// }// memset(vis,0,sizeof(vis));memset(pe,inf,sizeof(pe));// clear(q);for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){if(map[i][j]=='J'){pe[i][j]=0;q.push(make_pair(i,j));break;}}bfs_person();// for(int i=1;i<=n;++i){// for(int j=1;j<=m;++j)// cout<<pe[i][j]<<' ';// cout<<endl;// }//return; } int main(){int t;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);for(int i=1;i<=n;++i){scanf("%s",(map[i]+1));}solve();}return 0; } //除了上面的那个inf问题还有就是开始定义了两个vis的初始化，一开始就T掉，

POJ 3984 迷宫问题
定义一个二维数组：
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表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
Input
一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。
Output
左上角到右下角的最短路径，格式如样例所示。
Sample Input
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
Sample Output
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)

#include <cstdio> #include <iostream> #include <queue> //#include <bits/stdc++.h> #include <cstring> using namespace std; int mat[5][5]; int dir[5][2]={{1,0},{0,1},{0,-1},{-1,0}}; struct node{ int x,y,pre; }point[100]; void dfs(node p) {if(p.pre==-1){printf("(%d, %d)\n",p.x,p.y);return;}dfs(point[p.pre]);printf("(%d, %d)\n",p.x,p.y); } void bfs() {int x,y,dx,dy,pre=0,cur=1;//queue<node> q;point[0].x=0,point[0].y=0,point[0].pre=-1;mat[0][0]=1;while(pre<=cur){if(point[pre].x==4&&point[pre].y==4){dfs(point[pre]);return ;}for(int i=0;i<4;++i){dx=point[pre].x+dir[i][0];dy=point[pre].y+dir[i][1];if(dx<0||dx>=5||dy<0||dy>=5||mat[dx][dy])continue;point[cur].x=dx,point[cur].y=dy,point[cur].pre=pre;++cur;}++pre;} } int main() {for(int i=0;i<5;++i)for(int j=0;j<5;++j)scanf("%d",&mat[i][j]);bfs(); return 0; }

 

《新程序员》：云原生和全面数字化实践50位技术专家共同创作，文字、视频、音频交互阅读

总结

以上是生活随笔为你收集整理的【POJ3126 Prime Path】【POJ 3087 Shuffle'm Up】【UVA 11624 Fire!】【POJ 3984 迷宫问题】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。