第二十一周代码（java + DFS/BFS）

2024/03/04 周一

路径之谜

题目链接

【参考代码】

dfs剪枝

#include <iostream>
#include <vector>
using namespace std;

int n;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
bool visit[21][21] = {false};
int north[21], west[21];
vector<int> path;
bool flag = false;

void pathAddBlockNumber(int x, int y)
{
    path.push_back(x * n + y);
}

bool check()
{
    for(int i=0;i<n;i++)
    {
        if(north[i] != 0 || west[i] != 0)
            return false;
    }
    return true;
}

void dfs(int startx, int starty)
{ 
    if(north[starty] < 0 || west[startx] < 0) //剪枝，错误类型
        return;
    if(startx == n-1 && starty == n-1 && check()) //结束条件
    { //打印路径
        for(int i=0; i<path.size(); i++)
        {
            printf("%d ", path[i]);
        }
        return;
    }
    
    for(int i=0;i<4;i++)
    {
        int nowx = startx + dx[i];
        int nowy = starty + dy[i];
        if(visit[nowx][nowy] || nowx < 0 || nowx >= n || nowy < 0 || nowy >= n)
            continue;
        visit[nowx][nowy] = true;
        north[nowy]--, west[nowx]--;
        pathAddBlockNumber(nowx, nowy);

        dfs(nowx, nowy);
        visit[nowx][nowy] = false;
        north[nowy]++, west[nowx]++;
        path.pop_back();
    }
}

int main()
{
  scanf("%d", &n);
  //cin>>n;
  for(int i=0;i<n;i++)
  {
      scanf("%d", &north[i]);
  }
  for(int i=0;i<n;i++)
  {
      scanf("%d", &west[i]);
  }
  north[0]--,west[0]--; //(0,0)处的计数值先各减1 
  visit[0][0] = true; //(0,0)已访问 
  path.push_back(0); //路径加入0这个点
  dfs(0, 0);
  return 0;
}

2024/03/05 周二

P1025 [NOIP2001 提高组] 数的划分

题目链接

【参考代码】

#include <iostream>
using namespace std;

int count = 0;
int n, k;

//后一个数必须大于等于前一个数
void dfs(int nextnumber, int step, int sum)
{
    if(step == k) //分完step步，都要结束掉
    {
    	if(sum == n) //符合条件的结果+1
        	count++; 
        return;
    }
    //for(int i=nextnumber; i <= (n-sum)/(k-step); i++)
    for(int i=nextnumber; i <= n-sum; i++)
    {
        dfs(i, step+1, sum + i);
    }
}


int main()
{
    cin>>n>>k;
    dfs(1, 0, 0);
    cout << count;
}