c++ dfs 求调
查看原帖
c++ dfs 求调
1093380
zhangfengkai001楼主2024/5/1 16:53
#include <iostream>
#include<cstring>
#include<string>
#pragma G++ optimize(2)
using namespace std;
int n, m, a[20][20], mbx, mby, kbx, kby, X[4] = { 0,0,-1,1 }, Y[4] = {-1,1,0,0};
string s="";
char bx, by;

bool yn(int x, int y);
void dfs(int x, int y);

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> a[i][j];
        }
    }
    cin >> kbx >> kby >> mbx >> mby;
    bx = (char)kbx - '0', by = (char)kby - '0';
    dfs(kbx,kby);
    return 0;
}

bool yn(int x, int y)
{
    if (x <= 0 || x > n || y <= 0 || y > n || a[x][y] == '0') return false;
    return true;
}

void dfs(int x, int y)
{
    //cout << s << endl;
    if (x != kbx && x != kby)
    {
        s+="->"+ '(' + bx + ',' + by + ')';
    }
    if (x == mbx && y == mby)
    {
        cout << s << endl;
        s.clear();
        s = '(' + bx + ',' + by + ')';
        return;
    }
    for (int i = 0; i < 4; i++)
    {
        if (yn(x + X[i], y + Y[i]))
        {
            a[x + X[i]][y + Y[i]] = '0';
            dfs(x + X[i], y + Y[i]);
            a[x + X[i]][y + Y[i]] = '1';
        }
    }
    return;
}

2024/5/1 16:53
加载中...