POJ1256 && 1979 深搜入门

2019-04-15 14:54发布

站内文章 / PIC单片机
11994 0 1185
什么是深搜，我现在的理解是：用递归加上一些条件的限制去遍历
 简单题，经典题：POJ1526 UVA5712 #include #include #define M 105 char pic[M][M]; int m,n,idx[M][M]; void DFS(int r,int c,int id) { if(r <0 || r >= m || c < 0 || c >= n) return ; //边界处理 if(idx[r][c] > 0 || pic[r][c] != '@') return ; idx[r][c] = id; //id顾名思义，说明它属于哪一个油田 for(int dr = -1;dr <= 1; dr++) //上下左右的判断 for(int dc = -1;dc <= 1; dc++) if(dc != 0 || dr != 0) DFS(dr + r,dc + c,id); } int main() { while(scanf("%d%d",&m,&n) == 2 && n && m){ for(int i = 0;i < m; i++) scanf("%s",pic[i]); memset(idx,0,sizeof(idx)); int cnt = 0; for(int i = 0;i < m; i++) for(int j = 0;j < n; j++) if(idx[i][j] == 0 && pic[i][j] == '@') //把每一个点找个遍 DFS(i,j,++cnt); printf("%d ",cnt); } return 0; }
POJ1979
//题意：从点@出发问能走多少步，‘#’不能走，‘.可以走’ #include #include using namespace std; #define M 100 char map[M][M]; int m,n,sum; int coor[4][2] = {{-1,0},{1,0},{0,-1},{0,1}}; int judge(int x,int y) //很好的坐标的用法 { if(x < 0 || x >= m || y < 0 || y >= n) return 0; return 1; } void DFS(int x,int y) { int xx,yy; sum ++; map[x][y] = '#'; //每次改变，避免重复 for(int i = 0;i < 4; i++){ xx = x + coor[i][0]; yy = y + coor[i][1]; if(judge(xx,yy) && map[xx][yy] == '.') DFS(xx,yy); } } int main() { int x,y; // freopen("input.txt","r",stdin); while(scanf("%d%d",&n,&m) == 2 && n && m){ sum = 0; for(int i = 0;i < m; i++){ for(int j = 0;j < n; j++){ cin>>map[i][j]; if(map[i][j] == '@'){ x = i; y = j; } } } DFS(x,y); //很巧妙 printf("%d ",sum); } return 0; }
现在写的好看一点。 #include int n,m; char str[1000][1000]; int a,b,ans; int dir[4][2] = {{-1,0},{1,0},{0,1},{0,-1}}; void dfs(int x,int y) { ans++; str[x][y] = '#'; for(int i = 0;i < 4; i++){ int xx = x + dir[i][0]; int yy = y + dir[i][1]; if(xx < 1 || xx > m || yy < 1 || yy > n) continue ; if(str[xx][yy] == '.'){ dfs(xx,yy); } } } int main() { //freopen("in.txt","r",stdin); while(scanf("%d%d",&n,&m) != EOF){ if(n == 0 && m == 0) break; getchar(); for(int i = 1;i <= m; i++){ for(int j = 1;j <= n; j++){ scanf("%c",&str[i][j]); if(str[i][j] == '@'){ a = i; b = j; } } getchar(); } str[a][b] = '.'; ans = 0; dfs(a,b); printf("%d ",ans); } return 0; }

热门文章