深度优先搜索DFS,从最开始状态出发,遍历一种状态到底,再回溯搜索第二种。
题目:POJ2386
思路:(⊙v⊙)嗯 和例题同理啊,从@开始,搜索到所有可以走到的地方,把那里改为一个值(@或者真值什么的),最后遍历一遍地图就好了。
/* input: 7 7 ..#.#.. ..#.#.. ###.### ...@... ###.### ..#.#.. ..#.#.. 表示有13个可以走到的地方(包括原来那一格)。*/ #include <stdio.h> ][]; void solve(int H,int W); void find1(int H,int W); void dfs(int x,int y,int H,int W); int main() { int H,W,i; &&W!=) { getchar(); ;i<H;i++) gets(ch[i]); find1(H,W); solve(H,W); } ; } void solve(int H,int W) { ; ;i<H;i++) ;k<W;k++) if(ch[i][k]=='@') a++; printf("%d\n",a); } void find1(int H,int W) { ;i<H;i++) ;k<W;k++) if(ch[i][k]=='@') { dfs(i,k,H,W); return; } } void dfs(int x,int y,int H,int W) { int x1,y1,nx,ny; ch[x][y]='@'; ;x1<=;x1++) { nx=x+x1; &&nx<H&&ch[nx][y]!='#'&&ch[nx][y]!='@') dfs(nx,y,H,W); } ;y1<=;y1++) { ny=y+y1; &&ny<W&&ch[x][ny]!='#'&&ch[x][ny]!='@') dfs(x,ny,H,W); } return; }
POJ2386
练习题系列………………………………………………………
#include <stdio.h> ][]; void solve(int H,int W); void find1(int H,int W); void dfs(int x,int y,int H,int W); int main() { int H,W,i; &&W!=) { getchar(); ;i<H;i++) gets(ch[i]); find1(H,W); solve(H,W); } ; } void solve(int H,int W)//计数 { ; ;i<H;i++) ;k<W;k++) if(ch[i][k]=='@') a++; printf("%d\n",a); } void find1(int H,int W)//找到点 { ;i<H;i++) ;k<W;k++) if(ch[i][k]=='@') { dfs(i,k,H,W); return; } } void dfs(int x,int y,int H,int W) { int x1,y1,nx,ny; ch[x][y]='@'; ;x1<=;x1++) { nx=x+x1; &&nx<H&&ch[nx][y]!='#'&&ch[nx][y]!='@') dfs(nx,y,H,W); } ;y1<=;y1++) { ny=y+y1; &&ny<W&&ch[x][ny]!='#'&&ch[x][ny]!='@') dfs(x,ny,H,W); } return; }
POJ1979
#include <stdio.h> #include <iostream> using namespace std; ][]; ]={,,,-}; ]={,,-,}; int H,W,cou; void DFS(int x, int y){ ; char b=ch[x][y]; ch[x][y]='.'; ; i < ; i++) { int xn = x + xx[i], yn = y + yy[i]; && xn < W && yn >= && yn < H && ch[xn][yn] == b) { DFS(xn, yn); } } return ; } int main() { while(cin >> W >> H && (H && W)) { cou = ; ; i < W; i++) ; k < H; k++) cin >> ch[i][k]; ; i < W; i++) ; k < H; k++) if(ch[i][k] != '.') { DFS(i, k); cou++; } cout << cou << endl; } ; }
AOJ0033
题目:POJ3009
这题撸了很久。
#include <iostream> #include <string.h> #include <algorithm> using namespace std; ]={ , , -, }; ]={ , , , -}; ][]; int xn,yn,x1,y1,H,W,y2,x2,a; void dfs(int x1, int y1, int step){ ) return ; ; i < ; i++){//四个方向 int xn = x1 + dx[i], yn = y1 + dy[i]; if(xn == x2 && yn == y2){ a=min(a, step + ); continue; } )continue; && xn < W && yn >= && yn < H){ xn += dx[i]; yn += dy[i];//继续往下面走 && xn < W && yn >= && yn < H) { ) continue;//直到撞墙或终点 if(xn == x2 && yn == y2){//到达终点 a= min(a, step + ); return ; } map1[xn][yn] = ;//停下来了,继续dfs,注意dfs前后面的墙。 dfs(xn - dx[i], yn - dy[i], step + ); map1[xn][yn] = ; break; } } } return ; } int main() { && W != ){ ; i < W; i++) ; k < H; k++){ cin >> map1[i][k]; ){ x1 = i; y1 = k; map1[i][k] = ; } ){ x2 = i; y2 = k; map1[i][k] = ; } } a = ; dfs(x1, y1, ); || a>) cout << "-1" << endl; else cout << a <<endl; } ; }
POJ3009