深度优先搜索 dfs可视化【递归 && 非递归】

亦凉 2022-10-09 04:49 180阅读 0赞

打印了栈的大小，总觉得dfs不能直观的感受 ，  
打印了一下变化的过程

#include <iostream>
    #include <set>
    #include <vector>
    #include <map>
    #include <stack>
    #include <tuple>
    #include <algorithm>
    #include <iterator>
    #include <unordered_set>
    #include <windows.h>
    #include <time.h>
    #define debug(x) cout<<#x<<": "<<(x)<<endl;
    
    using namespace std;
    
    #define N (10)
    
    int g[N][N];
    
    int dx[4] = {  1,-1,0,0 };
    int dy[4] = {  0,0,1,-1 };
    stack<pair< int, int>>st;
    
    bool print() { 
    
    	Sleep(500);
    	system("cls");
    	
    	for (int i = 0; i < N; ++i) { 
    		for (int j = 0;j< N;++j) { 
    			if (g[i][j] == 0) { 
    				cout << "□";
    			}
    			else { 
    				cout << "■";
    			}
    		}
    		cout << endl;
    	}
    	cout<<"stack size: "<< st.size()<< " " << string(st.size(), '#') << endl;;
    	return true;
    }
    
    bool ver(int x,int y){ 
    	
    	
    	if (x >= 0 && x < N && y >= 0 && y < N) { 
    		return true;
    	}
    	return false;
    }
    
    bool dfs(int x,int y) { 
    	print();
    	for (int i = 0; i < 4; ++i) { 
    		if (ver(x + dx[i], y + dy[i]) && g[x + dx[i]][y+dy[i]] == 0) { 
    			g[x + dx[i]][y + dy[i]] = 1;
    			dfs(x + dx[i], y + dy[i]);
    		}
    	}
    	return true;
    }
    
    int main() { 
    	
    	fill(g[0], g[0] + N*N, 0);
    	
    	/*dfs(N/2,N/2); return 0;*/
    
    	print();
    	st.push({  N/2,N/2 });
    	g[5][5] = 1;
    	while (!st.empty()) { 
    		auto p = st.top();
    		//st.pop();
    		int x = p.first;
    		int y = p.second;
    		
    		print();
    		int i = 0;
    		for (i = 0; i < 4; ++i) { 
    			if (ver(x + dx[i], y + dy[i]) && g[x + dx[i]][y + dy[i]] == 0) { 
    				g[x + dx[i]][y + dy[i]] = 1;
    				st.push({  x + dx[i], y + dy[i] });
    				break;
    			}
    		}
    		if (i == 4) { 
    			st.pop();
    		}
    	}
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0wxNTU4MTk4NzI3_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0wxNTU4MTk4NzI3_size_16_color_FFFFFF_t_70]: /images/20221005/6f3ce450981545fbb88c9dee579c72f9.png