题意分析

题目描述了一个$10x10$的网格沼泽，其中某些位置有树桩（用'*'表示），其余位置是开放空间（用'.'表示）。我们需要从左上角$（1,1）$的树桩出发，通过放置木板连接到右下角$（10,10）$的树桩。木板只能水平或垂直放置，且必须从一个树桩开始和结束。每个木板只能使用一次，且必须使用给定的长度。题目可能有多解，只需找到任意一个可行解即可。

解题思路

输入处理：首先读取$10x10$的网格，标记树桩的位置。然后读取每个问题的木板数量和长度。

深度优先搜索（DFS）：从起点（0,0，对应网格的1,1）开始，尝试向四个方向（上、下、左、右）放置木板。每次放置木板时，检查目标位置是否在网格内、是否是树桩且未被访问过。

回溯法：如果当前木板放置后无法到达终点，则撤销该木板的放置（标记为未访问），并尝试其他木板或方向。

递归终止条件：当到达终点（9,9，对应网格的10,10）时，记录路径并返回成功。

输出结果：如果找到解，输出所有放置的木板信息；否则输出“no solution possible”。

参考代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
using namespace std;
typedef long long ll;
char M[20][20];
bool vis[20][20];
int plk[50],n;
char msg[50][100],mc;
bool proc(int i,int j,int p,int d);
bool dfs(int i,int j,int d){
    if(i==9&&j==9) {
        mc=d;
        return true;
    }
    for(int p=0;p<n;p++){
        int pl=plk[p];
        if(pl==0) continue;
        plk[p]=0;
        if(proc(i+pl,j,p,d)) return true;
        if(proc(i-pl,j,p,d)) return true;
        if(proc(i,j+pl,p,d)) return true;
        if(proc(i,j-pl,p,d)) return true;
        plk[p]=pl;
    }
    return false;
}
bool proc(int i,int j,int p,int d){
    if(!(i>=0&&i<10&&j>=0&&j<10&&M[i][j]=='*'&&!vis[i][j])) return false;
    vis[i][j]=true;
    bool r=dfs(i,j,d+1);
    if(r) sprintf(msg[d],"place plank %d to stump (%d,%d)",p+1,i+1,j+1);
    vis[i][j]=false;
    return r;
}
int main(){
    for(int i=0;i<10;i++){
        scanf("%s",M[i]);
    }
    bool rt=false;
    vis[0][0]=true;
    while(scanf("%d",&n)!=EOF){
        if(rt) printf("\n");
        rt=true;
        for(int i=0;i<n;i++){
            scanf("%d",&plk[i]);
        }
        if(dfs(0,0,0)){
            for(int i=0;i<mc;i++){
                printf("%s\n",msg[i]);
            }
        } else {
            printf("no solution possible\n");
        }
    }
    return 0;
}