A.迷宫问题 POJ 3984
bfs + 输出路径
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <queue> using namespace std; int maze[5][5]; int way[4][2] = {0,1,1,0,-1,0,0,-1}; struct node { int x,y,s,pre; node(int a,int b,int c,int d) {x = a; y = b; s = c; pre = d;} node(){} }ans[110]; int sta[105]; void bfs() { queue<node> q; q.push(node(0,0,0,-1)); int num = 0; while(!q.empty()) { node temp = q.front(); q.pop(); ans[num++] = temp; int x = temp.x,y = temp.y; if(x == 4 && y == 4) break; for(int i = 0; i < 4; i++) { int newx = x + way[i][0] , newy = y + way[i][1]; if(maze[newx][newy] || newx < 0 || newx > 4 || newy < 0 || newy > 4) continue; maze[newx][newy] = 1; node no = node(newx,newy,temp.s+1,num-1); q.push(no); } } int th = num - 1, snum = 0; while(ans[th].pre != -1) { sta[++snum] = ans[th].pre; th = ans[th].pre; } while(snum != 0) { printf("(%d, %d)\n",ans[sta[snum]].x,ans[sta[snum]].y); snum--; } printf("(4, 4)\n"); } int main() { for(int i = 0; i < 5; i++) for(int j = 0; j < 5; j++) scanf("%d",&maze[i][j]); bfs(); return 0; } B.棋盘问题 POJ 1321#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> using namespace std; int col[10]; int maze[10][10]; int n,m; char s[15]; int ans = 0; void dfs(int nowr,int num) { if(num == m) { ans++ ; return;} if(nowr >= n) return; for(int i = 0; i < n; i++) { if(maze[nowr][i] || col[i]) continue; col[i] = 1; dfs(nowr+1,num+1); col[i] = 0; } dfs(nowr + 1, num); } int main() { while(~scanf("%d%d",&n,&m)) { if(n == -1 && m == -1) break; for(int i = 0; i < n; i++) { scanf("%s",s); for(int j = 0; j < n ; j++) maze[i][j] = s[j] == '#'?0:1; } ans = 0; dfs(0,0); printf("%d\n",ans); } return 0; } C.三维迷宫问题 POJ 2251
#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <queue> using namespace std; const int maxn = 35; struct node { int x,y,z,s; node(int a,int b,int c,int d){x = a; y = b; z = c; s = d;} }; int maze[maxn][maxn][maxn]; int way[6][3] = {0,0,1,0,0,-1,0,1,0,0,-1,0,1,0,0,-1,0,0}; int st[3],p[3]; char s[100]; int m,n,Q; void bfs() { queue<node > q; q.push(node(st[0],st[1],st[2],0)); int flag = 0; maze[st[0]][st[1]][st[2]] = 1; while(!q.empty()) { node temp = q.front(); q.pop(); int x = temp.x, y = temp.y, z = temp.z, s = temp.s; if(x == p[0] && y == p[1] && z == p[2]) { flag = 1; printf("Escaped in %d minute(s).\n",s); break; } for(int i = 0; i < 6; i++) { int nx = x + way[i][0], ny = y + way[i][1] , nz = z + way[i][2]; if(maze[nx][ny][nz] || nx < 0 || nx >= m || ny < 0 || ny >= n || nz < 0 || nz >= Q) continue; maze[nx][ny][nz] = 1; q.push(node(nx,ny,nz,s+1)); } } if(!flag) printf("Trapped!\n"); } int main() { while(~scanf("%d%d%d",&m,&n,&Q) && n+m+Q) { for(int i = 0; i < m; i++) for(int j = 0; j < n; j++) { scanf("%s",s); for(int k = 0; k < Q;k ++) { maze[i][j][k] = 0; if(s[k] == 'S') st[0] = i,st[1] = j,st[2] = k; else if(s[k] == 'E') p[0] = i,p[1] = j,p[2] = k; else if(s[k] == '#') maze[i][j][k] = 1; } } bfs(); } return 0; } D.一个追牛的人的问题，记得空间别开小，会gg POJ 3278
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <queue> using namespace std; const int maxn = 1e5 + 10; int n,k; struct node { int v,s; node(int a,int b){v = a; s = b;} }; int vis[maxn*2]; int bfs() { queue<node> q; q.push(node(n,0)); for(int i = 0; i < maxn; i++) vis[i] = 0; vis[n] = 1; while(!q.empty()) { node temp = q.front(); q.pop(); if(temp.v == k) { printf("%d\n",temp.s); break; } int nx = temp.v + 1,ns = temp.s + 1; if(nx <= k + 1 && !vis[nx]) {vis[nx] = 1;q.push(node(nx,ns));} nx = temp.v * 2; if(nx < 2*k && !vis[nx]) {vis[nx] = 1;q.push(node(nx,ns));} nx = temp.v-1; if(nx >= 0 && !vis[nx]) {vis[nx] = 1;q.push(node(nx,ns));} } } int main() { while(~scanf("%d%d",&n,&k)) bfs(); return 0; } E.这个应该叫开关问题 POJ 3279
#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> using namespace std; int ori[20][20]; int op[20][20]; int moni[20][20]; int way[4][2] = {0,1,0,-1,1,0,-1,0}; int n,m; bool ans = false; void filp(int i,int j) { moni[i][j] = !moni[i][j]; for(int x = 0; x < 4; x++) { int nx = i + way[x][0] , ny = j + way[x][1]; if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue; moni[nx][ny] = !moni[nx][ny]; } } void conti(int time) { for(int i = 1; i < n; i++) for(int j = 0; j < m; j++) { if(moni[i-1][j]) {op[i][j] = 1;filp(i,j);} } int flag = 1; for(int i = 0; i < m; i++) if(moni[n-1][i]) { flag = 0; break;} if(flag) { ans = true; for(int i = 0; i < n ; i++) { for(int j = 0; j < m ; j++) j == 0?printf("%d",op[i][j]) : printf(" %d",op[i][j]); printf("\n"); } } } void solve() { ans = false; for(int i = 0; i < (1 << m); i++) //翻转第一行的全部情况 { if(ans) break; memset(op,0,sizeof(op)); memcpy(moni,ori,sizeof(ori)); int x = 0; for(int j = 1; j <= i; j = (1<<x)) { if((j&i) == j) {op[0][x] = 1, filp(0,x);} x++; } conti(i); } if(ans == false) printf("IMPOSSIBLE\n"); } int main() { while(~scanf("%d%d",&n,&m)) { for(int i = 0; i < n ; i++) for(int j = 0; j < m ; j++) scanf("%d",&ori[i][j]); solve(); } return 0; }
F.一个非要素数的问题 POJ 3126
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <queue> #include <cmath> using namespace std; int a,b; struct node { int to,s; int val[4]; node(){} node(int a,int b) { to = a; s = b; val[0] = to/1000, val[1] = to/100, val[2] = to/10, val[3] = to; } }; int prime[10000]; int vis[10000]; bool isPrime(int n) { // cout << n <<endl; int temp = (int)sqrt(n*1.0); for(int i = 2; i <= temp ; i++) if(n%i == 0) return 0; return 1; } void pre() { for(int i = 1000; i < 10000; i++) if(isPrime(i)) prime[i] = 1; } int bfs() { memset(vis,0,sizeof(vis)); queue<node> q; q.push(node(a,0)); vis[a] = 1; while(!q.empty()) { node temp = q.front(); q.pop(); int to = temp.to, s = temp.s; if(to == b) {printf("%d\n",s); break;} int nval[4]; for(int i = 0; i < 4; i++) nval[i] = temp.val[i]; for(int i = 0; i < 4; i++) for(int j = 0; j < 10; j++) { int newval = 0; for(int k = 0; k < 4; k++) if(k != i) newval = (newval * 10) + nval[k]; else newval = (newval*10) + j; if(!vis[newval] && prime[newval]) vis[newval] = 1, q.push(node(newval,s+1)); } } } int main() { pre(); int t; scanf("%d",&t); while(t--) { scanf("%d%d",&a,&b); bfs(); } return 0; } G. HDU 1010
一个我已经写过还是超时的问题
记得需要奇偶剪枝。
#include <iostream> #include <cstdio> #include <cstring> #include <queue> #include <cmath> using namespace std; const int inf = 0x3f3f3f3f; const int maxn = 10; int maze[maxn][maxn]; bool vis[maxn][maxn]; int way[4][2] = {1,0,-1,0,0,-1,0,1}; int s[2],p[2]; int n,m,t; bool ans = false; int dis(int x,int y) { int thdis = abs(x-p[0]) + abs(y-p[1]); return thdis; } int dfs(int x,int y,int step) { if(x == p[0] && y == p[1] && step == t){ans = true; return 1;} if(ans) return 1; if(step + dis(x,y) > t) return 0; for(int i = 0; i < 4; i++) { int newx = x + way[i][0] , newy = y + way[i][1]; if(!vis[newx][newy] && newx >= 0 && newx < n && newy >= 0 && newy < m && maze[newx][newy] == 0 && step + 1 <= t) { int mdis = dis(newx,newy); if(((t - (step+1) - mdis)%2)) return 0; vis[newx][newy] = 1; if(dfs(newx,newy,step+1)) return 1; vis[newx][newy] = 0; } } return 0; } char str[1000]; int main() { while(~scanf("%d%d%d",&n,&m,&t) && n+m+t) { ans = 0; memset(vis,0,sizeof(vis)); for(int i = 0 ; i < n ; i++) { scanf("%s",str); for(int j = 0 ; j < m ; j++) { maze[i][j] = 0; if(str[j] == 'S') s[0] = i, s[1] = j; else if(str[j] == 'D') p[0] = i, p[1] = j; else if(str[j] == 'X') maze[i][j] = 1; } } vis[s[0]][s[1]] = 1; dfs(s[0],s[1],0); vis[s[0]][s[1]] = 0; int sdis = dis(s[0],s[1]); if((t - sdis) % 2 != 0 || t < sdis) {printf("NO\n"); continue;} ans == 1 ? printf("YES\n") : printf("NO\n"); } return 0; } H.比油田更简单的flood fill HDU 1312
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; int maze[30][30]; char str[1000]; int st[2]; int way[4][2] = {0,1,0,-1,-1,0,1,0}; int ans = 0,n,m; void dfs(int x,int y) { ans ++; for(int i = 0; i < 4; i++) { int nx = x + way[i][0], ny = y + way[i][1]; if(!maze[nx][ny] && nx >= 0 && ny >= 0 && nx < n && ny < m) { maze[nx][ny] = 1; dfs(nx,ny); } } } int main() { while(~scanf("%d%d",&m,&n) && n+m) { ans = 0; for(int i = 0; i < n; i++) { scanf("%s",str); for(int j = 0; j < m; j++) { maze[i][j] = 0; if(str[j] == '#') maze[i][j] = 1; if(str[j] == '@') st[0] = i,st[1] = j; } } maze[st[0]][st[1]] = 1; dfs(st[0],st[1]); printf("%d\n",ans); } return 0; } I.油田问题
比上面那个稍稍难一点的flood fill HDU 1241
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; int maze[150][150]; char str[1000]; int st[2]; int way[8][2] = {0,1,0,-1,-1,0,1,0,1,1,1,-1,-1,1,-1,-1}; int ans,n,m; void dfs(int x,int y) { for(int i = 0; i < 8; i++) { int nx = x + way[i][0], ny = y + way[i][1]; if(!maze[nx][ny] && nx >= 0 && ny >= 0 && nx < n && ny < m) { maze[nx][ny] = 1; dfs(nx,ny); } } } int main() { while(~scanf("%d%d",&n,&m) && n+m) { ans = 0; for(int i = 0; i < n; i++) { scanf("%s",str); for(int j = 0; j < m; j++) { maze[i][j] = 0; if(str[j] == '*') maze[i][j] = 1; } } for(int i = 0; i < n ; i++) for(int j = 0; j < m ; j++) { if(maze[i][j] == 0) { ans ++; maze[i][j] = 1; dfs(i,j); } } printf("%d\n",ans); } return 0; } J.论如何逃出火灾现场问题 UVA 11624
什么，一个bfs不行？那就两个好了
#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #include <queue> using namespace std; const int maxn = 1050; const int inf = 0x3f3f3f3f; char str[maxn]; int Time[maxn][maxn]; int maze[maxn][maxn]; int vis[maxn][maxn]; int f[maxn][2],J[2]; int way[4][2] = {1,0,-1,0,0,1,0,-1}; int fnum = 0,n,m; struct node { int x,y,t; node(int a,int b,int c){x = a ; y = b ; t = c ;} }; void bfspre() { memset(vis,0,sizeof(vis)); memset(Time,inf,sizeof(Time)); queue<node> q; for(int i = 0; i < fnum; i++) { vis[ f[i][0] ][f [i][1] ] = Time[f[i][0]][f[i][1]] = 1; q.push(node(f[i][0],f[i][1],0)); } while(!q.empty()) { node temp = q.front(); q.pop(); int x = temp.x, y = temp.y, t = temp.t; Time[x][y] = t; for(int i = 0; i < 4; i++) { int nx = x + way[i][0] , ny = y + way[i][1]; if(nx < 0 || nx >= n || ny < 0 || ny >= m || maze[nx][ny]) continue; if(!vis[nx][ny]) { vis[nx][ny] = 1; q.push(node(nx,ny,t+1)); } } } } void bfs() { queue<node>q; q.push(node(J[0],J[1],0)); maze[J[0]][J[1]] = 1; int mark = 0; while(!q.empty()) { node temp = q.front(); q.pop(); int x = temp.x, y = temp.y, t = temp.t; for(int i = 0; i < 4; i++) { int nx = x + way[i][0] , ny = y + way[i][1]; if(nx < 0 || ny < 0 || nx >= n || ny >= m) { printf("%d\n",t + 1); mark = 1; break; } if(maze[nx][ny]) continue; if(!maze[nx][ny] && t + 1 < Time[nx][ny]) { maze[nx][ny] = 1; q.push(node(nx , ny , t+1)); } } if(mark) break; } if(!mark) printf("IMPOSSIBLE\n"); } int main() { int t; scanf("%d",&t); while(t--) { fnum = 0; scanf("%d%d",&n,&m); for(int i = 0; i < n; i++) { scanf("%s",str); for(int j = 0; j < n; j++) { maze[i][j] = 0; if(str[j] == '#') maze[i][j] = 1; if(str[j] == 'F') f[fnum][0] = i, f[fnum++][1] = j; if(str[j] == 'J') J[0] = i, J[1] = j; } } bfspre(); bfs(); } return 0; } K.闲着无聊倒水玩儿问题 POJ 3414
#include <cstdio> #include <algorithm> #include <cstring> #include <iostream> #include <queue> using namespace std; struct node { int i,j,s,way,pre; node(){} node(int a,int b,int c,int d){i = a; j = b; s = c;pre = d;} }pro[1005]; bool vis[105][105]; int anum = 1; int a,b,c; char out[10][20] = {" ","FILL(1)", "FILL(2)", "DROP(1)" , "DROP(2)", "POUR(1,2)", "POUR(2,1)"}; void print(int id) { if(pro[id].pre != 1) print(pro[id].pre); printf("%s\n",out[pro[id].way]); } void bfs() { int mark = 0; anum = 1; memset(vis,0,sizeof(vis)); queue<node > q; q.push(node(0,0,0,0)); while(!q.empty()) { node temp = q.front(); q.pop(); pro[anum++] = temp; int x = temp.i, y = temp.j, s = temp.s; //cout << x <<" " << y << endl; if(x == c || y == c) { printf("%d\n",s); print(anum-1); mark = 1; break; } node change = node(a,y,s+1,anum-1); if(!vis[a][y]) change.way = 1, vis[a][y] = 1,q.push(change); change.i = x, change.j = b; if(!vis[x][b]) change.way = 2,vis[x][b] = 1,q.push(change); change.i = 0, change.j = y; if(!vis[0][y]) change.way = 3,vis[0][y] = 1,q.push(change); if(!vis[x][0]) change.way = 4, vis[x][0] = 1,change.i = x, change.j = 0,q.push(change); if(y+x > b) { change.i = y+x-b, change.j = b; if(!vis[y+x-b][b]) vis[y+x-b][b] = 1, change.way = 5, q.push(change); } else { change.i = 0, change.j = y+x; if(!vis[0][y+x]) vis[0][y+x] = 1, change.way = 5, q.push(change); } if(x+y > a) { change.i = a, change.j = x+y-a; if(!vis[a][x+y-a]) vis[a][x+y-a] = 1, change.way = 6, q.push(change); } else { change.i = x+y, change.j = 0; if(!vis[x+y][0]) vis[x+y][0] = 1,change.way = 6,q.push(change); } } if(!mark) printf("impossible\n"); } int main() { while(~scanf("%d%d%d",&a,&b,&c)) { bfs(); } return 0; } L.并不是bfs + dfs 只是模拟题 POJ 3087
#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> using namespace std; char s1[150],s2[150]; char temp1[150], temp2[150]; char sta[300],tar[300]; int main() { int t,n; scanf("%d",&t); for(int kase = 1; kase <= t; kase ++) { scanf("%d",&n); scanf("%s%s%s",s1,s2,tar); int num = 0; while(num < 10000) { for(int i = 0; i < 2*n; i++) sta[i] = i%2?s1[i/2] : s2[i/2]; sta[2*n] = '\0'; num++; if(strcmp(sta,tar) == 0) break; for(int i = 0; i < n; i++) s1[i] = sta[i]; s1[n] = '\0'; for(int i = n; i <= 2*n; i++) s2[i-n] = sta[i]; s2[2*n] = '\0'; // cout << sta << " " << s1 << " " << s2 << endl; } printf("%d ",kase); if(num == 10000) printf("-1\n"); else printf("%d\n",num); } return 0; }
