杭电 1495 非常可乐
#include <iostream> #include <cstdio> #include <vector> #include <cstring> #include <queue> using namespace std; int s,n,m,mark[110][110],ff; struct node{ int ss,nn,mm,step; }u,v; void bfs(){ queue<node>q; u.ss=s,u.nn=0,u.mm=0,u.step=0,mark[u.ss][u.nn]=1; q.push(u); while(!q.empty()){ u=q.front(),q.pop(); if((u.ss==u.nn&&u.mm==0)){ ff=1; printf("%d\n",u.step); return ; } v.ss=u.ss-(n-u.nn);///s倒入n if(v.ss>=0){ v.mm=u.mm;v.nn=n; if(mark[v.ss][v.nn]==0) mark[v.ss][v.nn]=1,v.step=u.step+1,q.push(v); } else{ v.mm=u.mm;v.ss=0;v.nn=u.nn+u.ss; if(mark[v.ss][v.nn]==0) mark[v.ss][v.nn]=1,v.step=u.step+1,q.push(v); } v.ss=u.ss-(m-u.mm);///s倒入m if(v.ss>=0){ v.nn=u.nn;v.mm=m; if(mark[v.ss][v.nn]==0) mark[v.ss][v.nn]=1,v.step=u.step+1,q.push(v); } else{ v.nn=u.nn;v.ss=0;v.mm=u.mm+u.ss; if(mark[v.ss][v.nn]==0) mark[v.ss][v.nn]=1,v.step=u.step+1,q.push(v); } v.nn=u.nn-(s-u.ss);///n倒入s if(v.nn>=0){ v.mm=u.mm;v.ss=s; if(mark[v.ss][v.nn]==0) mark[v.ss][v.nn]=1,v.step=u.step+1,q.push(v); } else{ v.mm=u.mm;v.nn=0;v.ss=u.ss+u.nn; if(mark[v.ss][v.nn]==0) mark[v.ss][v.nn]=1,v.step=u.step+1,q.push(v); } v.nn=u.nn-(m-u.mm);n倒入m if(v.nn>=0){ v.ss=u.ss;v.mm=m; if(mark[v.ss][v.nn]==0) mark[v.ss][v.nn]=1,v.step=u.step+1,q.push(v); } else{ v.ss=u.ss;v.nn=0;v.mm=u.mm+u.nn; if(mark[v.ss][v.nn]==0) mark[v.ss][v.nn]=1,v.step=u.step+1,q.push(v); } v.mm=u.mm-(s-u.ss);///m倒入s if(v.mm>=0){ v.nn=u.nn;v.ss=s; if(mark[v.ss][v.nn]==0) mark[v.ss][v.nn]=1,v.step=u.step+1,q.push(v); } else{ v.nn=u.nn;v.mm=0;v.ss=u.ss+u.mm; if(mark[v.ss][v.nn]==0) mark[v.ss][v.nn]=1,v.step=u.step+1,q.push(v); } v.mm=u.mm-(n-u.nn);///m倒入n if(v.mm>=0){ v.ss=u.ss;v.nn=n; if(mark[v.ss][v.nn]==0) mark[v.ss][v.nn]=1,v.step=u.step+1,q.push(v); } else{ v.ss=u.ss;v.mm=0;v.nn=u.nn+u.mm; if(mark[v.ss][v.nn]==0) mark[v.ss][v.nn]=1,v.step=u.step+1,q.push(v); } } } int main() { int t; while(scanf("%d %d %d",&s,&n,&m)&&n&&m&&s){ ff=0;memset(mark,0,sizeof(mark)); if(n<m){ t=n,n=m,m=t; }///分出大小利于只考虑两个杯子 bfs(); if(ff==0) printf("NO\n"); } return 0; }
poj 3126 prime path
#include<cstdio> #include<cstring> #include<queue> #define INF 0x3f3f3f3f using namespace std; int n,m,p[10000],l=0,a[10000],mark[10000],ff,t[5]; struct node{ int x,step; }u,v; ///筛选素数 void prim(){ int i,j; for(i=2;i<10000;i++){ if(!a[i]) p[l++]=i; for(j=0;j<l&&i*p[j]<10000;j++)//筛选过程 { a[i*p[j]]=1; if(i%p[j]==0) break; } } } void bfs(){ int i,j,temp; queue<node>q; u.x=n,u.step=0,mark[n]=1; q.push(u); while(!q.empty()){ u=q.front(),q.pop(); if(u.x==m){ ff=1; printf("%d\n",u.step); return ; } t[0]=u.x/1000,t[1]=u.x%1000/100,t[2]=u.x%100/10,t[3]=u.x%10; for(j=0;j<4;j++){ temp=t[j]; for(i=0;i<10;i++){ if (j==0&&i==0) continue;///最高为0没意义 if(i!=temp){ t[j]=i; v.x=t[0]*1000+t[1]*100+t[2]*10+t[3]; if(!mark[v.x]&&!a[v.x]){ //未被标记且是素数 v.step=u.step+1; mark[v.x]=1; q.push(v); } } } t[j]=temp; } } } int main() { int i,j,T; prim(); scanf("%d",&T); while(T--){ scanf("%d %d",&n,&m); memset(mark,0,sizeof(mark)); bfs(); if(ff==0) printf("Impossible\n"); } return 0; }
poj 1426 find the multiple
#include<cstdio> #include<cstring> #include<queue> #define INF 0x3f3f3f3f using namespace std; long long n;//注意类型 void bfs(){ long long x,y,z=1; queue<long long>q;//类型 q.push(z); while(!q.empty()){ z=q.front(),q.pop(); if(z%n==0){ printf("%lld\n",z); return ; } x=z*10; q.push(x); y=z*10+1; q.push(y); } } int main() { int i,j; while(scanf("%lld",&n)&&n){ bfs(); } return 0; }
hdu 1241 oil Deposits
#include<cstdio> #include<cstring> #include<queue> #define INF 0x3f3f3f3f using namespace std; int mark[110][110],n,m,flag; int dir[8][2]={{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};; char mapp[110][110]; struct node{ int x,y,step; }u,v; bool judge(int x,int y){ if(x>=0&&x<n&&y>=0&&y<m&&mark[x][y]==0&&mapp[x][y]=='@') return true; return false; } void dfs(int x,int y){ int i,xx,yy; mark[x][y]=1; for(i=0;i<8;i++){ xx=x+dir[i][0]; yy=y+dir[i][1]; if(judge(xx,yy)) dfs(xx,yy); } } int main() { int i,j; while(scanf("%d %d",&n,&m)&&n&&m){ getchar(); for(i=0;i<n;i++){ for(j=0;j<m;j++) scanf("%c",&mapp[i][j]); getchar(); } memset(mark,0,sizeof(mark)); flag=0; for(i=0;i<n;i++) for(j=0;j<m;j++) if(mapp[i][j]=='@'&&mark[i][j]==0){ dfs(i,j); flag++; } printf("%d\n",flag); } return 0; }
hdu 2612 find a way
#include<cstdio> #include<cstring> #include<queue> #define INF 0x3f3f3f3f using namespace std; int mark[210][210],dist[210][210][2],n,m,flag; int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; char mapp[210][210]; struct node{ int x,y,step; }u,v; bool judge(int x,int y){ if(x>=0&&x<n&&y>=0&&y<m&&mark[x][y]==0&&mapp[x][y]!='#') return true; return false; } void bfs(int x,int y){ int i; queue<node>q; u.x=x,u.y=y,u.step=0,mark[x][y]=1; q.push(u); while(!q.empty()){ u=q.front(),q.pop(); for(i=0;i<4;i++){ v.x=u.x+dir[i][0]; v.y=u.y+dir[i][1]; if(judge(v.x,v.y)){ mark[v.x][v.y]=1; v.step=u.step+1; if(mapp[v.x][v.y]=='@') dist[v.x][v.y][flag]=v.step; q.push(v); } } } } int main() { int i,j; while(scanf("%d %d",&n,&m)!=EOF){ for(i=0;i<n;i++) for(j=0;j<m;j++) dist[i][j][0]=dist[i][j][1]=INF;//记得初始化为无穷 getchar(); for(i=0;i<n;i++){ for(j=0;j<m;j++) scanf("%c",&mapp[i][j]); getchar(); } for(i=0;i<n;i++) for(j=0;j<m;j++){ if(mapp[i][j]=='Y'){ memset(mark,0,sizeof(mark)); flag=0; bfs(i,j); } if(mapp[i][j]=='M'){ memset(mark,0,sizeof(mark)); flag=1; bfs(i,j); } } int minn=INF; for(i=0;i<n;i++) for(j=0;j<m;j++) if(mapp[i][j]=='@'&&minn>dist[i][j][0]+dist[i][j][1]) minn=dist[i][j][0]+dist[i][j][1]; printf("%d\n",minn*11); } return 0; }
