hdu 2102 A计划
#include <iostream> #include <stdio.h> #include <string.h> #include <queue> using namespace std; char mapp[3][11][11]; int mark[3][11][11],n,m,times,ff; int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; struct node { int x,y,z,step; }u,v; void bfs(int sx,int sy,int sz){ queue<node>q; int i; u.x=sx,u.y=sy,u.z=sz,u.step=0;mark[sz][sx][sy]=1; q.push(u); while(!q.empty()){ u=q.front(),q.pop(); if(mapp[u.z][u.x][u.y]=='P'&&u.step<=times){ ff=1; printf("YES\n"); return ; } for(i=0;i<4;i++){ v.x=u.x+dir[i][0]; v.y=u.y+dir[i][1]; v.z=u.z; if(v.x>=0&&v.x<n&&v.y>=0&&v.y<m&&v.z>=0&&v.z<2&&(mapp[v.z][v.x][v.y]=='.'||mapp[v.z][v.x][v.y]=='P')&&mark[v.z][v.x][v.y]==0){ mark[v.z][v.x][v.y]=1; v.step=u.step+1; q.push(v); } if(v.x>=0&&v.x<n&&v.y>=0&&v.y<m&&v.z>=0&&v.z<2&&mapp[v.z][v.x][v.y]=='#'&&mark[v.z][v.x][v.y]==0){ if((mapp[!v.z][v.x][v.y]=='*'||mapp[!v.z][v.x][v.y]=='#')&&mark[!v.z][v.x][v.y]==0){ mark[v.z][v.x][v.y]=1; } else{//注意 mark[v.z][v.x][v.y]=1; v.step=u.step+1; v.z=!v.z; q.push(v); } } } } } int main() { int T,i,j,k,sx,sy,sz; scanf("%d",&T); while(T--){ scanf("%d %d %d",&n,&m,×); getchar(); for(i=0;i<2;i++){ for(j=0;j<n;j++){ for(k=0;k<m;k++){ scanf("%c",&mapp[i][j][k]); if(mapp[i][j][k]=='S') sx=j,sy=k,sz=i; } getchar(); } getchar(); } memset(mark,0,sizeof(mark));ff=0; bfs(sx,sy,sz); if(ff==0) printf("NO\n"); } return 0; }
hdu 1728 逃离迷宫（转弯问题）
#include <iostream> #include <stdio.h> #include <string.h> #include <queue> using namespace std; int mark[202][202],n,m,K,ff,dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; char mapp[202][202]; struct node{ int x,y,turn_num; }u,v; void bfs(int sx,int sy,int ex,int ey){ queue <node> q; int i; u.x=sx;u.y=sy;u.turn_num=-1;mark[sx][sy]=1; q.push(u); while (!q.empty()) { u=q.front();q.pop(); if (u.x==ex&&u.y==ey&&u.turn_num<=K) ff=1; v.turn_num = u.turn_num + 1; for (i=0;i<4;i++){ v.x = u.x + dir[i][0]; v.y = u.y + dir[i][1]; while(v.x>=1&& v.x<=n&&v.y>=1&&v.y<=m&&mapp[v.x][v.y]=='.') { if (!mark[v.x][v.y]) q.push(v),mark[v.x][v.y]=1; v.x += dir[i][0]; v.y += dir[i][1]; } } } } int main() { int T,i,j,sx,sy,ex,ey; scanf("%d",&T); while(T--){ scanf("%d %d",&n,&m); getchar(); for(i=1;i<=n;i++){ for(j=1;j<=m;j++) scanf("%c",&mapp[i][j]); getchar(); } scanf("%d %d %d %d %d",&K,&sy,&sx,&ey,&ex); memset(mark,0,sizeof(mark));ff=0; bfs(sx,sy,ex,ey); if(ff==0) printf("no\n"); else printf("yes\n"); } return 0; }
bfs+优先队列
hdu 3152 （dp数组存和）
#include <iostream> #include <stdio.h> #include <string.h> #include <queue> #define inf 0x3f3f3f3f using namespace std; int mark[210][210],n,dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; int mapp[210][210],dp[210][210]; bool judge(int x,int y){ if(x<0||x>=n||y<0||y>=n) return false; return true; } void bfs(){ queue<int>qx,qy; int i,j,ux,uy,dx,dy; for(i=0;i<n;i++) for(j=0;j<n;j++) dp[i][j]=inf; dp[0][0]=mapp[0][0]; qx.push(0);qy.push(0); while(!qx.empty()&&!qy.empty()){ ux=qx.front(),qx.pop(); uy=qy.front(),qy.pop(); for(i=0;i<4;i++){ dx=ux+dir[i][0]; dy=uy+dir[i][1]; if(judge(dx,dy)&&dp[dx][dy]>dp[ux][uy]+mapp[dx][dy]){ dp[dx][dy]=dp[ux][uy]+mapp[dx][dy]; qx.push(dx); qy.push(dy); } } } } int main() { int i,j,ff=0; while(scanf("%d",&n)&&n){ for(i=0;i<n;i++) for(j=0;j<n;j++) scanf("%d",&mapp[i][j]); bfs(); printf("Problem %d: %d\n",++ff,dp[n-1][n-1]); } return 0; }
hdu 1242 resuce
#include <iostream> #include <cstdio> #include <vector> #include <cstring> #include <queue> using namespace std; const int N = 215; struct node{ int x,y,step; friend bool operator<(node n1,node n2) { return n2.step<n1.step; } }u,v; char map[N][N]; int vis[N][N],n,m,dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}},ff,ans; void bfs(int x,int y){ priority_queue<node> q; int i; u.x=x,u.y=y,u.step=0,vis[x][y]=1; q.push(u); while(!q.empty()){ u=q.top(),q.pop(); if(map[u.x][u.y]=='r'){ ff=1; printf("%d\n",u.step); return ; } for(i=0;i<4;i++){ v.x=u.x+dir[i][0]; v.y=u.y+dir[i][1]; if(v.x>=0&&v.x<n&&v.y>=0&&v.y<m&&vis[v.x][v.y]==0&&(map[v.x][v.y]=='.'||map[v.x][v.y]=='r')) vis[v.x][v.y]=1,v.step=u.step+1,q.push(v); if(v.x>=0&&v.x<n&&v.y>=0&&v.y<m&&vis[v.x][v.y]==0&&map[v.x][v.y]=='x') vis[v.x][v.y]=1,v.step=u.step+2,q.push(v); } } } int main() { int i,j,k; while(~scanf("%d%d",&n,&m)){ ff=0;ans=0x3f3f3f3,memset(vis,0,sizeof(vis)); for(i=0;i<n;i++){ getchar(); for(j=0;j<m;j++) scanf("%c",&map[i][j]); } for(i=0;i<n;i++) for(j=0;j<m;j++) if(map[i][j]=='a') bfs(i,j); if(ff==0) printf("Poor ANGEL has to stay in the prison all his life.\n"); } return 0; }
hdu 1180 诡异的电梯
/* 5 5 **..T **.*. ..|.. .*.*. S.... Sample Output 7 */ #include <stdio.h> #include <algorithm> #include <iostream> #include <queue> #include <string.h> using namespace std; const int N = 50; const int INF = 0x3f3f3f3f; char Map[N][N]; int n, m, vis[N][N], dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; struct node { int x, y, step; friend bool operator < (const node &a, const node &b) { return a.step > b.step; } }st,u,v; bool check(int x, int y) { if(x >= 0 && x < n && y >= 0 && y < m && !vis[x][y] && Map[x][y] != '*') return true; else return false; } int bfs(int x, int y) { char c; priority_queue <node> q; u.x = x;u.y = y;u.step = 0;vis[u.x][u.y] = 1; int i; q.push(u); while(!q.empty()) { u = q.top(),q.pop(); for(i = 0; i < 4; i ++) { v.x =u.x+ dir[i][0]; v.y =u.y+ dir[i][1]; v.step =u.step+ 1; if(check(v.x, v.y) && (Map[v.x][v.y] == '-' || Map[v.x][v.y] == '|')) { if(v.step % 2 == 1) { if(Map[v.x][v.y] == '-') c = '|'; else if(Map[v.x][v.y] == '|') c = '-'; } else c = Map[v.x][v.y]; v.x =v.x+ dir[i][0]; v.y =v.y+ dir[i][1]; if((c == '-' && (dir[i][1] == -1 || dir[i][1] == 1)) || (c == '|' && (dir[i][0] == -1 || dir[i][0] == 1))) { v.step += 1; } } if(check(v.x, v.y)) { if(Map[v.x][v.y] == 'T') return v.step; vis[v.x][v.y] = 1; q.push(v); } } } return -1; } int main() { int i,j; while(~scanf("%d%d",&n,&m)) { getchar(); for(i= 0; i < n; i ++){ for(j = 0; j < m; j ++) { scanf("%c",&Map[i][j]); if(Map[i][j] == 'S') st.x = i,st.y = j; } getchar(); } memset(vis, 0, sizeof(vis)); int ans = bfs(st.x, st.y); printf("%d\n", ans); } return 0; }奇偶剪枝
hdu 1010
#include<iostream> #include<cstring> #include <stdio.h> #include <math.h> #define N 10 using namespace std; int n,m,t,ex,ey,visited[N][N],flag,ans; char map[N][N]; int abs(int a,int b) { if(a<b) return b-a; return a-b; } void dfs(int i,int j,int c) { if(flag) return ; if(c>t) return ; if(i<0||i>=n||j<0||j>=m) {return ;} if(map[i][j]=='D'&&c==t) {flag=ans=1; return ;} int temp=abs(i,ex)+abs(j,ey); temp=t-temp-c; if(temp&1) return ;//奇偶剪枝 if(!visited[i-1][j]&&map[i-1][j]!='X') { visited[i-1][j]=1; dfs(i-1,j,c+1); visited[i-1][j]=0; } if(!visited[i+1][j]&&map[i+1][j]!='X') { visited[i+1][j]=1; dfs(i+1,j,c+1); visited[i+1][j]=0; } if(!visited[i][j-1]&&map[i][j-1]!='X') { visited[i][j-1]=1; dfs(i,j-1,c+1); visited[i][j-1]=0; } if(!visited[i][j+1]&&map[i][j+1]!='X') { visited[i][j+1]=1; dfs(i,j+1,c+1); visited[i][j+1]=0; } } int main() { int i,j,x,y,k; while(scanf("%d %d %d",&n,&m,&t)&&(m||n||t)){ memset(visited,0,sizeof(visited));k=0; getchar(); for(i=0;i<n;i++) { for(j=0;j<m;j++) { scanf("%c",&map[i][j]); if(map[i][j]=='S') { x=i;y=j; visited[i][j]=1; } if(map[i][j]=='D') ex=i,ey=j; if(map[i][j]=='X')k++; } getchar(); } ans=flag=0; if(n*m-k-1>=t) dfs(x,y,0); if(ans) printf("YES\n"); else printf("NO\n"); } return 0; }
FZU 2150 fire game
#include <iostream> #include <cstdio> #include <vector> #include <cstring> #include <queue> using namespace std; const int N = 15; struct node{ int x,y; int cnt ; }; vector<node> v; char mp[N][N]; int vis[N][N],n,m,dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; int BFS(node a,node b){ memset(vis,0,sizeof(vis)); queue<node> q; int i; vis[a.x][a.y] = vis[b.x][b.y] = 1; a.cnt = 0,b.cnt = 0; q.push(a),q.push(b); int ans = 0x3f3f3f3f; int cas = 1; while(!q.empty()) { a = q.front(),q.pop(); ans=a.cnt; for(i=0;i<4;i++){ b.x=a.x+dir[i][0]; b.y=a.y+dir[i][1]; b.cnt=a.cnt+1; if(b.x>0&&b.x<=n&&b.y>0&&b.y<=m&&vis[b.x][b.y]==0&&mp[b.x][b.y]=='#') vis[b.x][b.y] = 1,q.push(b); } } return ans; } int main() { int T,cas,i,j,k,f; scanf("%d",&T); for(cas=1;cas<=T;cas++) { v.clear(); scanf("%d%d",&n,&m); for(i=1;i<=n;i++) { getchar(); for(j=1;j<=m;j++){ scanf("%c",&mp[i][j]); if(mp[i][j]=='#') v.push_back((node){i,j,0}); } } int ans = 0x3f3f3f3f,tmp; for(i=0;i<v.size();i++){ for(j=i;j<v.size();j++){ tmp=BFS(v[i],v[j]); bool ok = true; for(k = 1;k<=n;k++) { for(f = 1;f<=m;f++) { if(vis[k][f] == 0 && mp[k][f]=='#') { ok = false; break; } } if(ok==false) break; } if(ok) { ans = min(ans,tmp); } } } printf("Case %d: ",cas); if(ans == 0x3f3f3f3f) puts("-1"); else printf("%d\n",ans); } return 0; }
