第五周总结

本周学习的重心依然在算法，因为比较难（哭），所以进度很慢，但是基本上每一道dfs的题都用了至少五小时的时间去理解，dfs实在是太难了！！！

心得：
dfs非常典型的自底向上的搜索，当写dfs时要弄清楚函数的意义以方便清晰知道返回值应该是什么，避免越写越乱，

个人小技巧： 当实在想不明白返回值时，可以从最简单的情况也就是自底向上的底仔细考虑，Eg: 当写dfs返回子树的个数时，可以先想叶子节点返回的值，从而推算出返回值（下述第三题）。

附上经典题目：

１.

TIM图片20200217141440.png

#include <iostream>
 using namespace std;
 
const int N = 10;
int n;
 int path[N];
 bool flag[N];
 
 void dfs(int u)
 {
     if(u == n) 
     {
         for(int i=0; i<n; i++) printf("%d ", path[i]);
         puts("");
         return;
     }
     
     
 for(int i=1; i<=n ;i++)
     {
        if(!flag[i])
         {
              path[u] = i;
              flag[i] = true;
              dfs(u+1);
              flag[i] = false;
         }
     }
     
 }
 int main()
 {
     
     cin>>n;
     dfs(0);
 }

２.

2.png

#include <iostream>
using namespace std;

const int N = 20;
bool row[N], col[N], dig[N], udig[N];
char g[N][N];
int n;

void dfs(int r)
{
    // row[r] = true;
    if(r == n) 
     {
         for(int i=0; i<n; i++)
           {
               for(int j=0; j<n; j++)  cout<<g[j];
                cout<<endl;
           }
           cout<<endl;
     }
     
     for(int i=0; i<n; i++)
     {
         if(!col[i] && )
     }
}

int main()
{
    cin>>n;
    memset(g, '.', sizeof(g));
    dfs(0);
}

３.

3.png

#include <iostream>
#include <cstring>
 using namespace std;
 
const int N = 100010;
int n;
int e[2*N], ne[2*N], h[N], idx = 0;
int asw = N;
bool flag[N];


void add(int a , int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx;
    idx++;
}

//返回不包括 u 在内的子树的所有节点
int dfs(int u)
{
    int res = 0;//最大联通个数
    // int tmp = 0; //return , 返回不包括 u 在内的子树的所有节点
    int total_child = 0;
    flag[u] = true;
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(!flag[j])
        {
            int s = dfs(j) + 1;
            res = max(res, s);
            total_child += s;
        }
        
    }
       res = max(res, n - total_child - 1);
        asw = min(asw, res);
        return total_child;
}
 int main()
 {
     cin>>n;
     int a,b;
     memset(h, -1, sizeof(h));
     for(int i=0; i<n-1; i++)
     {
         scanf("%d%d", &a, &b); 
         add(a, b);  add(b, a);
     }
     dfs(e[0]);
     cout<<asw;
 }

收获： 学会了用数组去模拟图的存储（邻接矩阵），^ . ^

４、

4.png

#include <iostream>
#include <cstring>
#include <queue>
 using namespace std;
 
typedef pair<int,int> PII;
int n,m;
const int N = 110;
int g[N][N]; //存储图
int dis[N][N]; //到原点的距离
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0,-1,0, 1}; //上，左，下 ，右

int bfs()
{
    queue<PII> q;
    memset(dis, -1, sizeof(dis));
    dis[0][0] = 0;
    q.push({0,0});
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        for(int i=0; i<4; i++)
         {
             int x = t.first + dx[i];
             int y = t.second + dy[i];
             if(x>=0 && x<n && y>=0 && y<m && g[x][y] == 0 && dis[x][y] == -1) 
               {
                   dis[x][y] = dis[t.first][t.second] + 1;
                   q.push({x,y});
               }
         }
         
    }
    return dis[n-1][m-1];
}
 int main()
 {
  
  cin>>n>>m;
  for(int i=0; i<n; i++)
    for(int j=0; j<m; j++)
      cin>>g[i][j];
  cout<<bfs();
 }

收获：当权值一样时，求最短路径一般是用BFS