蓝桥杯2016年第七届真题-路径之谜 （C++代码）

解题思路:DFS+剪枝

建一个表，(i:1->N)arr[i][0]存西边箭数，arr[0][i]存北边箭数，中间部分为0或1用来表示是否是旧点；
从(1,1)开始深搜，目标为(N,N)。深搜过程中每到一个点，将该点标记为旧点，对应位置的靶子的箭的数量自减1，并将走到的这个点存入最后会输出的ans[]，然后向这个点的上下左右继续深搜。
到达终点的条件：访问表arr，若北边靶的箭数量+西边靶的箭的数量=2(即只剩下N,N的箭没有拔)，则找了目标路径，否则继续深搜知道找到为止。

注意事项:

参考代码:

#include <iostream>
#include <stdlib.h>
using namespace std;
 
int arr[22][22]={0}; //(i-1)*N + j - 1
int ans[410];
int count_ans=0;
int N;
 
 bool dfs(int i, int j)
 {
     if(i == N && j == N)
     {
         //判断是否所有箭都中了
         int flag=0;
        for(int k=1; k<=N; k++)
        {
            flag+=arr[k][0];
            flag+=arr[0][k];
             if(flag>2)
                 break;
        }
        //已经找到这条路了
        if(flag == 2)
        {
            for(int k=0; k<count_ans; k++)
                cout<<ans[k]<<" ";
            cout<<N*N-1;
            return true;
        }
        else
            return false;
    }
    
    if(i<1 || i>N || j<1 || j>N)//剪枝3：超出范围
        return false;
    if(arr[i][j] != 0)//剪枝1：走过
        return false;
    if(arr[i][0] == 0 || arr[0][j] == 0)//剪枝2：箭不够了
        return false;
    
     arr[i][j]=1;//设为旧点，拔出箭 ，放入答案栈
     arr[i][0]--;
     arr[0][j]--;
     ans[count_ans++]= (i-1)*N + j - 1 ;
     if(dfs(i+1,j)||dfs(i-1,j)||dfs(i,j+1)||dfs(i,j-1))
         return true;
     count_ans--;//复原
     arr[i][0]++;
     arr[0][j]++;
     arr[i][j]=0;
     return false;
 }
 
int main()
{
    cin>>N;
    for(int i=0; i<N; i++)
        cin>>arr[0][i+1];
    for(int i=0; i<N; i++)
        cin>>arr[i+1][0];
 
    dfs(1,1);
 
    return 0;
}