题解 | #字符串加密#

C++最纯粹的解法

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

int min1=999,n=0,m=0;
int a[10][10] = {0};
int book[10][10] = {0};

void dfs(int x, int y, vector<pair<int,int> > &ans, int step,vector<pair<int ,int> > &ans_finsh)
{
    int fx[4][2] = {
        { 0, 1},//右
        { 1, 0},//下
        { 0,-1},//左
        {-1, 0}//上
    };
    //临界值，到达终点
    if(x==n-1 && y==m-1)
    {
        if(step < min1)
        {
            min1 = step;
            ans_finsh.clear();
            for(int i=0;i<ans.size();i++)
            {
                ans_finsh.push_back(ans[i]);
            }
        }
        return;
    }
    for(int k=0;k<4;k++)
    {
        int tx = x + fx[k][0];
        int ty = y + fx[k][1];
        //异常判断，越界、走过了，路障
        if(tx>n-1 || tx<0 || ty<0 || ty>m-1 || a[tx][ty] == 1 || book[tx][ty] == 1)
            continue;

        book[tx][ty] = 1;
        ans.push_back(make_pair(tx,ty));
        dfs(tx, ty, ans, step+1,ans_finsh);//下一步
        book[tx][ty] = 0;
        ans.pop_back();
    }
}

int main()
{
    while(cin >> n >> m)
    {
        min1 = 999;
        vector<pair<int ,int> > ans;
        vector<pair<int ,int> > ans_finsh;
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
            {
                cin>>a[i][j];
            }
        book[0][0] = 1;
        ans.push_back(make_pair(0,0));
        book[0][0] = 0;
        dfs(0,0,ans,0,ans_finsh);
        for(int i=0;i<ans_finsh.size();i++)
        {
            cout <<"("<<ans_finsh[i].first<<","<<ans_finsh[i].second<<")"<<endl;
        }
    }
    return 0;
}