正文索引 [隐藏]

A 中国象棋

在这里插入图片描述

一道挺标准的DFS模板，只不过走法换成了走日字。

#include <bits/stdc++.h>

using namespace std;

char g[10][9];
bool book[10][9];

int dx[] = { -2,-1,1,2,2,1,-1,-2 };
int dy[] = { 1,2,2,1,-1,-2,-2,-1 };

bool dfs(int x, int y)
{
    book[x][y] = true;
    if (g[x][y] == 'T')return true;

    for (int i = 0; i < 8; i++)
    {
        int tx = dx[i] + x, ty = dy[i] + y;
        if (tx < 0 || tx >= 10 || ty < 0 || ty >= 9) continue;
        if (book[tx][ty]) continue;
        if (g[tx][ty] == '#') continue;
        if (dfs(tx, ty)) return true;
    }
    return false;
}
int main()
{
    for (int i = 0; i < 10; i++)
		cin >> g[i];
    for (int i = 0; i < 10; i++)
        for (int j = 0; j < 9; j++)
            if (g[i][j] == 'S')
                if (dfs(i, j))cout << "Yes";
                else cout << "No";

    return 0;
}

B 踏青

遍历到草丛的时候向四周搜索，将能构成草地的草丛标记。
当走到没有被标记过得草丛时就是新的一片草地，cnt++就行了。

#include <bits/stdc++.h>

#define rep(a, b, c) for (int a = b; a <= c; a++)

using namespace std;

const int INF = 0X7F7F7F7F;
const int LIM = 105;

int n, m, cnt;
char g[LIM+1][LIM+1];
bool vis[LIM+1][LIM+1] = {0};
int dxy[4][2] = {{-1, 0}, {1,0}, {0,-1}, {0,1}};

void dfs(int x, int y)
{
	vis[x][y] = 1;
	for(int i = 0; i < 4; i++)
	{
		int dx = x + dxy[i][0];
		int dy = y + dxy[i][1];
		if(dx >= 1 && dx <= n && dy >= 1 && dy <= m && vis[dx][dy] == 0 && g[dx][dy] == '#')
			dfs(dx, dy);
	}
}

int main()
{
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
			cin >> g[i][j];
	
	for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
			if(g[i][j] == '#' && vis[i][j] == 0)
			{
				cnt++;
				dfs(i, j);
			}
	
	cout << cnt;
	return 0;
}

C 引爆炸弹

跟上一题挺像的。遍历到一个炸弹，就将跟他同行列的炸弹一起递归引爆。
这样每次遍历到一个vis=1的炸弹都一定是第一次遇见且之前没有被引爆的，计数器++就行。

#include<iostream>

using namespace std;

const int LIM = 1005;

char g[LIM][LIM];
int n, m, ans;

void dfs(int x, int y)
{
  g[x][y] = 0;
  for(int i = 0; i < m; i++)
  	if(g[x][i] == '1')
		dfs(x, i);
  for(int i = 0; i < n; i++)
  	if(g[i][y] == '1')
	  	dfs(i, y);
}

int main()
{
  cin >> n >> m;
   for(int i = 0;i < n; i++)
   	cin >> g[i];
  for(int i = 0; i < n; i++)
    	for(int j = 0; j < m; j++)
        	if(g[i][j] == '1')
			{
				dfs(i,j);
				ans++;
			}
			 
  cout << ans;
  return 0;
}

E超级书架2

#include <bits/stdc++.h>

#define rep(a, b, c) for (int a = b; a <= c; a++)

using namespace std;

const int INF = 0X7F7F7F7F;

int n, s, ans = INF;
int h[110];

void dfs(int now, int len, int sum, int b)
{
    if(sum >= b) 
		ans = min(sum-b, ans);
    else
        for(int i = now; i <= len; i++)
            dfs(i+1, len, sum+h[i], b);
}

int main()
{
	cin >> n >> s;
	for(int i = 0; i < n; i++) cin >> h[i];
	dfs(0, n, 0, s);
	cout << ans;
	return 0;
}

F自然数拆分

挺标准的dfs模板。

因为是按因子个数降序排列，所以核心代码块可以参考dfs模板给出下述伪代码：

for(int i = 1; i < n; i++)//因为是分解因子，所以是严格小于n
{
	if 符合条件
	{
		记录当前因子;
		往前一步;
		递归调用dfs继续往下找;
		回退一步; 
	} 
}

如果画出它的决策树的话，可以很清晰的看见就是走到没法走就回到父亲节点走另一个儿子，相当标准。

#include <iostream>
 
using namespace std;

int a[30];
 
int n;

void dfs(int sum, int len, int start) 
{
    if (n == sum) 
	{
        cout << n << "=" << a[0];
        for (int i=1; i<len; i++) 
            cout << "+" << a[i];
        cout << endl;
        return;
    }
    for (int i = 1; i < n; i++) 
	{
        if (sum+i <= n && i >= start) 
		{
            a[len] = i;
            len++;
            dfs(sum+i, len, i);
            len--;
        }
    }
}
 
int main() 
{
    cin >> n;
    dfs(0, 0, 1);
    return 0;
}