7 条题解

  • 0
    @ 2024-4-9 22:22:25

    //模板 #include <bits/stdc++.h> using namespace std; #define endl '\n' #define INF 0x3f3f3f3f3f3f3f3f

    //移动向量 int dx[4] = {-1,0,1,0}; int dy[4] = {0,-1,0,1};

    //创建迷宫 int a[42][42];

    //起点终点 pair<int , int> Start; pair<int , int> End;

    //迷宫大小 int n,m;

    //方案总数 int flag = 0;

    //第一次 int diyici = 1;

    //该点是否来过
    bool coming[42][42];

    //路线 vector<pair<int , int> > Path;

    void dfs(pair<int , int> now) { if(now == End) { Path.push_back(End);

    	for(int i = 0 ; i < Path.size() - 1 ; i++)
    	{
    		cout << "(" << Path[i].first + 1 << "," << Path[i].second + 1 << ")" << "->";
    	}
    	
    	cout << "(" << Path[Path.size() - 1].first + 1<< "," << Path[Path.size() - 1].second + 1 << ")" << endl;
    	
    	flag = 1;
    	
    	Path.pop_back();
    	coming[now.first][now.second] = 0;
    }
    
    
    for(int i = 0 ; i < 4 ; i++)
    {
    	Path.push_back(now);
    	
    	int nex = now.second + dx[i] , ney = now.first + dy[i];
    	if(nex >= 0 && nex < m && ney >= 0 && ney < n /*位置可取*/ && coming[ney][nex] != 1 /*下一个位置未去过*/ && a[ney][nex] == 1 /*此路可通*/)
    	{
    		coming[now.first][now.second] = 1;
    		coming[ney][nex] = 1;
    		
    		dfs({ney,nex});
    		
    		//回溯 
    		coming[now.first][now.second] = 0;
    		coming[ney][nex] = 0;
    	}
    	
    	Path.pop_back();
    }
    
    return;
    

    }

    signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    memset(coming , 0 , sizeof(coming) );
    memset(a , 0 , sizeof(a));
    
    //初始化迷宫  
    cin >> n >> m;
    for(int i = 0 ; i < n ; i++)
    {
    	for(int j = 0 ; j < m ; j++)
    	{
    		cin >> a[i][j];
    	}
    }
    
    //起点和终点  
    int First,Second;
    
    //(y,x)
    //first -- y
    //second -- x
    
    //起点 
    cin >> First >> Second;
    Start.first = First - 1;
    Start.second = Second - 1;
    
    //终点 
    cin >> First >> Second;
    End.first = First - 1; // y
    End.second = Second - 1; // x
    
    /*
    r(int i = 0 ; i < n ; i++)
    {           1      =
    	for(int j = 0 ; j < m ; j++)
    	{           1      =
    		cout << a[i][j];
    	}
    }
    
    cout << "(" << Start.first << "," << Start.second << ")" ;
    cout << "(" << End.first << "," << End.second << ")" ;
    
    auto temp = make_pair(1,1);
    
    if(Start == temp)
    {
    	cout << endl << "Right compare" << endl;
    }
    */
    
    dfs(Start);
    
    if(flag == 0)
    {
    	cout << "-1";
    }
    
    return 0;
    

    }

    信息

    ID
    84
    时间
    1000ms
    内存
    256MiB
    难度
    8
    标签
    递交数
    776
    已通过
    118
    上传者