[AcWing算法刷题]之DFS+BFS迷宫模板（简单）

题目来源：

题库 - AcWing

DFS和BFS模板题目：迷宫类

机器人的运动范围

字母

迷宫

红与黑

棋盘问题

马走日

全球变暖

DFS综合类

乘积最大（提高课）

单词接龙（提高课）

取石子游戏（dfs数学推理）

机器人的运动范围

BFS：

class Solution {
public:

    int get_sum(pair p) {
        int s = 0;
        while (p.first) {
            s += p.first % 10;
            p.first /= 10;
        }
        while (p.second) {
            s += p.second % 10;
            p.second /= 10;
        }
        return s;
    }

    int movingCount(int threshold, int rows, int cols)
    {
        if (!rows || !cols) return 0;
        queue> q;
        vector> st(rows, vector(cols, false));

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

        int res = 0;
        q.push({0, 0});
        while (q.size()) {
            auto t = q.front();
            q.pop();
            if (st[t.first][t.second] || get_sum(t) > threshold) continue;
            res ++ ;
            st[t.first][t.second] = true;
            for (int i = 0; i < 4; i ++ ) {
                int x = t.first + dx[i], y = t.second + dy[i];
                if (x >= 0 && x < rows && y >= 0 && y < cols) q.push({x, y});
            }
        }

        return res;
    }
};

DFS：

class Solution {
public:
int k;
int b,a;
int f[52][52];
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
    int movingCount(int threshold, int rows, int cols)
    {
        memset(f,false,sizeof f);
        b=cols,a=rows;

         int res=0;

        k=threshold;

        return    dfs(0,0);
    }
    int dfs(int y,int x)
    {
        if(x<0||x>=a||y<0||y>=b||f[y][x]) return 0;

         f[y][x]=true;
        int res=0;
        int x1=x,y1=y;
        while(x1)
        {
            res+=(x1%10);
            x1/=10;
        }
         while(y1)
        {
            res+=(y1%10);
            y1/=10;
        }

        if(res>k) return 0;
        int sum=0;

        for(int i=0;i<4;i++)
        {
            int q=x+dx[i],p=y+dy[i];
            sum+=dfs(p,q);
        }


         return sum+1;
    }
};

作者：dfbdberberb
链接：https://www.acwing.com/solution/content/11722/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

乘积最大（较难）

#include
#include
#include
using namespace std;

int n, k, ans;
string str;
bool st[20];//标记数字是否出现过
vectornum;//存放分割的数字

int number(int l, int r)//求区间[l,r]的数字
{
    int res = 0;
    for (int i = l; i <= r; i++)
        res = res * 10 + str[i] - '0';
    return res;
}

void dfs(int pos, int cnt)//枚举到的第几个空位，乘号的当前个数
{
    if (cnt == k)//如果乘号个数==题目所给的乘号个数
    {
        int y = number(pos, n - 1);//求出分割k次以后，第k+1个数的大小
        num.push_back(y);//放入分割的数字中
        int tmp = 1;
        for (int i = 0; i < num.size(); i++)//求乘积
            tmp *= num[i];
        //          cout<> n >> k;
    cin >> str;
    dfs(0, 0);
    cout << ans << endl;
    return 0;
}

字母

BFS：

需要额外开一个字母数组来哈希快速找到该字母是否之前已经走过

#include
#include
#include
#include
#include
#include
#include
using namespace std;

int n, m;
const int N = 50;
vector V;
int mp[26];

struct STATE {
	int x, y;
	int mp[26];
	int step;
};

int ans = -1;
int addx[4] = { 1,-1,0,0 };
int addy[4] = { 0,0,-1,1 };

void bfs()
{
	queue q;
	struct STATE s;
	memset(s.mp, 0, sizeof s.mp);
	s.mp[V[0][0] - 'A'] = 1;//标记
	s.step = 1;
	s.x = 0, s.y = 0;

	q.push(s);
	while (q.size())
	{
		auto t = q.front();
		q.pop();
		ans = max(ans, t.step);
		
		for (int i = 0; i < 4; i++)
		{
			int newx = t.x + addx[i];
			int newy = t.y + addy[i];
			
			if (newx >= 0 && newx < n && newy >= 0 && newy < m)
			{
				int idx = V[newx][newy] - 'A';
				if (t.mp[idx] == 1) continue;
				struct STATE next;
				next.x = newx;
				next.y = newy;
				next.step = t.step + 1;
				memcpy(next.mp, t.mp, sizeof t.mp);
				next.mp[idx] = 1;

				q.push(next);
			}
		}
	}
}

int main()
{
	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		string s;
		cin >> s;
		V.push_back(s);
	}

	bfs();
	cout << ans << endl;

	return 0;
}

DFS：

同样需要开一个字母数组，来判断该字母是否出现过

不同的地方在与DFS搜索迷宫具有对称性：标记（）搜索下一层（）取消标记

#include
#include
#include
#include
using namespace std;

int n, m;
const int N = 50;
vector V;
int mp[26];
int ans = -1;

int addx[] = { 1,-1,0,0 };
int addy[] = { 0,0,-1,1 };

void dfs(int x, int y, int step)
{
	int idx = V[0][0] - 'A';
	mp[idx] = 1;

	for (int i = 0; i < 4; i++)
	{
		int newx = x + addx[i];
		int newy = y + addy[i];

		if (newx >= 0 && newx < n && newy >= 0 && newy < m)
		{
			int idx = V[newx][newy] - 'A';
			if (mp[idx] == 1) continue;
			mp[idx] = 1;
			dfs(newx, newy, step + 1);
			mp[idx] = 0;
		}
	}
	ans=max(ans,step);
}

int main()
{
	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		string s;
		cin >> s;
		V.push_back(s);
	}

	dfs(0, 0, 1);
	cout << ans << endl;

	return 0;
}

迷宫

BFS：

#include
#include
#include
using namespace std;

typedef pair PII;
const int N = 110;
int n;
char g[N][N];
bool st[N][N];
queue q;
int startx, starty;
int endx, endy;

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

void bfs()
{
	q.push({ startx,starty });
	st[startx][starty]=true;
	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 < n && !st[x][y] && g[x][y] == '.')
			{
				st[x][y] = true;
				q.push({ x,y });
			}
			else continue;
		}
	}
}

int main()
{
	int T;
	cin >> T;
	while (T--)
	{
		cin >> n;
		for (int i = 0; i < n; i++) cin >> g[i];

		cin >> startx >> starty;
		cin >> endx >> endy;

		bfs();
		
        if(g[startx][starty]=='#' || g[endx][endy]=='#' || !st[endx][endy])cout << "NO" << endl;
		else if (st[endx][endy]) cout << "YES" << endl;
		

		memset(st, false, sizeof st);
	}

	return 0;
}

DFS：

#include 
#include 
#include 

using namespace std;

const int N = 110;

char g[N][N];
bool st[N][N];
int n;
int l1, r1, l2, r2;
int dx[] = {0, -1, 0, 1}, dy[] = {-1, 0, 1, 0};
bool dfs(int x, int y)
{
    if(x == l2 && y == r2)return true;
    st[x][y] = true;
    for(int i = 0; i < 4; i ++)
    {
        int a = x + dx[i], b = y + dy[i];
        if(a < 0 || a >= n || b < 0 || b >= n)continue;
        if(g[a][b] == '#')continue;
        if(st[a][b])continue;
        if(dfs(a, b))return true;
    }
    return false;
}

int main()
{
    int T;
    cin >> T;
    while(T --)
    {
        memset(st, false, sizeof st);
        cin >> n;
        for(int i = 0; i < n; i ++) cin >> g[i];
        cin >> l1 >> r1 >> l2 >> r2;
        if(g[l1][r1] == '#' || g[l2][r2] == '#')
        {
            puts("NO");
            continue;
        }
        if(dfs(l1, r1))puts("YES");
        else puts("NO");
    }
    return 0;
}

红与黑

DFS：

#include
#include
using namespace std;
const int N=25;
char g[N][N];
bool st[N][N];
int n,m;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};

int dfs(int x,int y)
{
    int cnt=1;
    st[x][y]=true;
    
    for(int i=0;i<4;i++)
    {
        int a=x+dx[i];
        int b=y+dy[i];
        if(a<0 || a>=n || b<0 || b>=m) continue;
        if(g[a][b]!='.') continue;
        if(st[a][b]) continue;
        
        cnt+=dfs(a,b);
    }
    return cnt;
}

int main()
{
	while (cin >> m >> n, n || m)
	{
		for (int i = 0; i < n; i++) cin >> g[i];

		int x, y;
		for(int i=0;i 

棋盘问题 
 
  
 
//DFS
//类似于八皇后的一道多了一些限制的题

#include 
#include 
#include 

using namespace std;

const int N = 20;

char g[N][N];                                       //存储输入棋盘 
int ans;                                            //存储答案 
int n, k;
int m;                                              //存储已近放入棋盘的棋子数 
bool line[N];                                       //存储当前列上有没有其他棋子 

void dfs(int x)
{
    if(m == k)                                      //当棋子放光的时候 
    {
        ans++;
        return;
    }

    if(x == n)                                      //防止越界 
        return;
    
    dfs(x + 1);     //这个是关键，因为 k <= m，因此可能有行不用放棋子，所以我们要手动舍弃行，直接进入下一行 
    for(int i = 0; i < n; i++)                      //爆搜 
        if(!line[i] && g[x][i] == '#')
        {
            line[i] = true;
            m++;                                    //记录放入的棋子数 
            dfs(x + 1);
            line[i] = false;                        //还原初始状态 
            m--;
        }

    
}

int main()
{
    while(scanf("%d%d", &n, &k) && n != -1 && k != -1)
    {
        ans = m = 0;
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                cin >> g[i][j];

        dfs(0);
        cout << ans << endl;
    }

    return 0;
}
 

取石子游戏 
 
  
 
#include
#include
using namespace std;

int n, m;

void dfs(int a, int b, int step)
{
	if (a % b == 0 || a / b >= 2)
	{
		if (step & 1)
		{
			cout << "win" << endl;
			return;
		}
		else
		{
			cout << "lose" << endl;
			return;
		}
	}
	dfs(b, a % b, step + 1);
}

int main()
{
	while (cin >> n >> m, n || m)
	{
		if (n < m) swap(n, m);
		if (n / m >= 2) cout << "win" << endl;
		else dfs(n, m, 1);
	}

	return 0;
} 

马走日 
 
 
#include
using namespace std;
int T,n,m,a,b,ans;
int vis[20][20];
int dx[8]={2,1,-1,-2,-2,-1,1,2};//方向数组
int dy[8]={1,2,2,1,-1,-2,-2,-1};//方向数组
void dfs(int x,int y,int step)//step记录当前走了几个格子
{
    if(step==n*m){//已遍历完所有的格子
        ans++;//答案加一
        return;
    }
    for(int i=0;i<8;i++){
        int kx=x+dx[i];
        int ky=y+dy[i];
        if(kx>=0&&kx=0&&ky 

单词接龙（提高课） 
 
  
 
#include 
#include 
#include 

using namespace std;

const int N = 21;

int n;
string word[N];
int g[N][N];//代表编号i的可以被j拼接  如i：asd，j：sdf，拼接长度为最小值g[i][j] = 2，i从0开始记位
int used[N];//编号为i的单词使用次数
int ans;

void dfs(string dragon, int last)
{
    ans = max((int)dragon.size(), ans);//取最大值，dragon.size()为当前合并的长度

    used[last]++;//编号为last的单词被用次数++；

    for (int i = 0; i < n; i++)
        if (g[last][i] && used[i] < 2)//used[i]<2代表单词用次数不超过2
            dfs(dragon + word[i].substr(g[last][i]), i); //编号为last的可以被i拼接现在尾巴为i号

    used[last]--;//恢复现场
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> word[i];
    char start;
    cin >> start;//首字母

    for (int i = 0; i < n; i++)//遍历得到各个g[i][j]
        for (int j = 0; j < n; j++) {
            string a = word[i], b = word[j];
            for (int k = 1; k < min(a.size(), b.size()); k++)
                if (a.substr(a.size() - k, k) == b.substr(0, k)) {
                    g[i][j] = k;
                    break;
                }
        }

    for (int i = 0; i < n; i++)//找到首字母为strat的单词开始做dfs，dfs中会自动找到最大值
        if (word[i][0] == start)
            dfs(word[i], i);//从word[i]开始遍历，i代表现在是第几个单词

    cout << ans << endl;

    return 0;
} 

全球变暖 
 
  
  
 
#include
#include
#include
#include
#define x first
#define y second
using namespace std;
typedef pair PII;
const int N = 1010;
int n;
char g[N][N];
bool st[N][N];
PII q[N * N];
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
// total : 岛屿的板块的数量  bound：邻接海洋的岛屿板块的数量
void bfs(int sx, int sy, int& total, int& bound)
{
	int hh = 0;
	int tt = 0;
	q[0] = { sx,sy };
	st[sx][sy] = true;

	while (hh <= tt)
	{
		PII t = q[hh++];

		total++;
		bool is_bound = false;
		for (int i = 0; i < 4; i++)
		{
			int x = t.x + dx[i];
			int y = t.y + dy[i];
			if (x < 0 || x >= n || y < 0 || y >= n) continue;
			if (st[x][y]) continue;//如果已经走过了
			if (g[x][y] == '.')//上下左右之中有一个为海
			{
				is_bound = true;
				continue;
			}
			q[++tt] = { x,y };
			st[x][y] = true;
		}
		if (is_bound) bound++;//只要上下左右之中有一个为海，那么它就是边界
	}
}

int main()
{
	cin >> n;

	for (int i = 0; i < n; i++) cin >> g[i];

	int cnt = 0;
	for(int i=0;i

[AcWing算法刷题]之DFS+BFS迷宫模板（简单）

C/C++/C#相关栏目本月热门文章