DFS BFS

路径之谜#include stdio.h #include stdlib.h int dx[]{1,0,-1,0}; int dy[]{0,1,0,-1}; int d[200]{0}; int j0; int num1; void dfs(int ab[][20],int a[][20],int b[],int c[],int x,int y,int n) { if(x0||xn||y0||yn) return; if(ab[x][y]!-1) return; if(b[x]0c[y]0) { ab[x][y]j; b[x]--; c[y]--; d[j]a[x][y]; j; if(xn-1yn-1) { for(int i0;in;i) { if(b[i]0c[i]0) num; } if(numn) { for(int i0;ij;i) { printf(%d ,d[i]); } return; } num0; } for(int i0;i4;i) { dfs(ab,a,b,c,xdx[i],ydy[i],n); } ab[x][y]-1; b[x]; c[y]; j--; } } int main(int argc, char *argv[]) { int n; int b[20],c[20]; scanf(%d,n); int a[20][20]; int ab[20][20]; for(int i0;in;i) { for(int j0;jn;j) { a[i][j]i*nj; ab[i][j]-1; } } for(int i0;in;i) { scanf(%d,c[i]); } for(int i0;in;i) { scanf(%d,b[i]); } dfs(ab,a,b,c,0,0,n); return 0; }数字三角形数字接龙#include stdio.h #include stdlib.h #include string.h int n,k; int g[11][11]; int dx[8]{-1,-1,0,1,1,1,0,-1}; int dy[8]{0,1,1,1,0,-1,-1,-1}; char path[121]; int path_len0; int st[11][11]; int edge[11][11][11][11]; int dfs(int a,int b) { if(an-1bn-1) { return path_lenn*n-1; } st[a][b]1; for(int i0;i8;i) { int xadx[i],ybdy[i]; if(x0||xn||y0||yn) continue; if(st[x][y]) continue; if(g[x][y]!(g[a][b]1)%k) continue; if(i%2(edge[a][y][x][b]||edge[x][b][a][y])) continue; edge[a][b][x][y]1; path[path_len]i0; if(dfs(x,y)) return 1; path_len--; edge[a][b][x][y]0; } st[a][b]0; return 0; } int main(int argc, char *argv[]) { scanf(%d %d,n,k); for(int i0;in;i) { for(int j0;jn;j) { scanf(%d,g[i][j]); } } memset(st,0,sizeof(st)); memset(edge,0,sizeof(edge)); path_len0; if(!dfs(0,0)) printf(-1\n); else { path[path_len]\0; printf(%s\n,path); } return 0; }飞机降落#include stdio.h #include stdlib.h #include string.h int max(int a,int b) { return ab?a:b; } typedef struct { int t,d,l; }Plane; Plane p[15]; int visit[15]; int flag; void dfs(int m,int cnt,int last) { if(cntm) { flag1; return; } for(int i0;im;i) { if(!visit[i](p[i].tp[i].d)last) { visit[i]1; dfs(m,cnt1,max(last,p[i].t)p[i].l); visit[i]0; if(flag) return ; } } } int main(int argc, char *argv[]) { int T; scanf(%d,T); while(T--) { int n; scanf(%d,n); for(int i0;in;i) { scanf(%d %d %d,p[i].t,p[i].d,p[i].l); } flag0; memset(visit,0,sizeof(visit)); dfs(n,0,0); if(flag) printf(YES\n); else printf(NO\n); } return 0; }五子棋对弈#include stdio.h #include stdlib.h int mp[5][5]; int u0; void dfs(int sum,int h,int b) { if(sum25) { if(h13b12) { for(int i0;i5;i) { int smp[i][0]mp[i][1]mp[i][2]mp[i][3]mp[i][4]; if(s5||s0) return ; } for(int i0;i5;i) { int mmp[0][i]mp[1][i]mp[2][i]mp[3][i]mp[4][i]; if(m5||m0) return; } int pmp[0][0]mp[1][1]mp[2][2]mp[3][3]mp[4][4]; int lmp[0][4]mp[1][3]mp[2][2]mp[3][1]mp[4][0]; if(p0||p5||l0||l5) return; u; } return; } int xsum/5; int ysum%5; mp[x][y]1; dfs(sum1,h1,b); mp[x][y]0; dfs(sum1,h,b1); } int main(int argc, char *argv[]) { dfs(0,0,0); printf(%d,u); return 0; }全球变暖#include stdio.h #include string.h int dx[]{1,-1,0,0}; int dy[]{0,0,1,-1}; int n,cnt0,flag1; int visit[1005][1005]{0}; char s[1005][1005]; void dfs(int sx,int sy) { visit[sx][sy]1; int has_water0; for(int i0;i4;i) { int xsxdx[i],ysydy[i]; if(x0||y0||xn||yn) continue; if(s[x][y].) { has_water1; continue; } if(!visit[x][y]s[x][y]#) dfs(x,y); } if(!has_water) flag0; } int main(int argc, char *argv[]) { scanf(%d,n); for(int i0;in;i) { scanf(%s,s[i]); } int cnt0; for(int i0;in;i) { for(int j0;jn;j) { if(s[i][j]#!visit[i][j]) { flag1; dfs(i,j); if(flag) cnt; } } } printf(%d,cnt); return 0; }N皇后问题#include stdio.h #include stdlib.h #include math.h #define MAX 10000 int a[MAX]; int ans0,n; int check(int row,int col) { for(int i1;irow;i) { if(a[i]col) return 0; if(abs(row-i)abs(col-a[i])) return 0; } return 1; } void dfs(int row) { if(rown1) { ans; return; } for(int col1;coln;col) { if(check(row,col)) { a[row]col; dfs(row1); a[row]0; } } } int main(int argc, char *argv[]) { scanf(%d,n); for(int i0;iMAX;i) { a[i]0; } dfs(1); printf(%d,ans); return 0; }玩具蛇#include stdio.h #include stdlib.h int dx[]{1,-1,0,0}; int dy[]{0,0,1,-1}; int visit[4][4]; int res0; void dfs(int x,int y,int len) { if(x0||x4||y0||y4) return; if(visit[x][y]1) return; if(len15) { res; return; } visit[x][y]1; for(int i0;i4;i) { dfs(xdx[i],ydy[i],len1); } visit[x][y]0; } int main(int argc, char *argv[]) { for(int i0;i4;i) { for(int j0;j4;j) { dfs(i,j,0); } } printf(%d,res); return 0; }