自动搬运

查看原文

来自洛谷，原作者为

	Err_BJT **

搬运于2025-08-24 21:32:18，当前版本为作者最后更新于2018-01-15 13:39:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

#一道简单的水题！

用普通的深搜就可以解决了，由于题目规定，只能往上或者向右走，就可以省去许多时间，反正是比迷宫那题简单多了。

#我把边和右边多一格的位置全部设置了-1，可以避免越界。

如果当前位置为-1的话，就返回上一个操作。

        #include<iostream>  //头文件，只有两个
        #include<cstdio>
        using namespace std;
        int s[20][20],ans,a,b; //s判断是否可以通过，abs表示方案总数。
        void dfs(int x,int y)  //深搜过程
        {
            int i;
            if (x==a&&y==b) { ans++;return;} //判断是否是否到达学校。
                     else
                      if (s[x][y]!=-1)  //判断此路径是否可以行走。
                       {
                           dfs(x,y+1); //向右走一格。
                           dfs(x+1,y); //向上走一格。
                       }
        }
        int main()
        {
            int n;
            cin>>a>>b;  //常规的输入。
            cin>>n;
            int x1,x2;
            for (int i=1;i<=n;i++)
            {
                cin>>x1>>x2;  //输入障碍的坐标。
                s[x1][x2]=-1;  //障碍的坐标我们赋值为-1，方便深搜判断。
            }
            for (int i=1;i<=a;i++)
             s[i][b+1]=-1;  //右边多一格的位置全部复制等于-1，避免越界。
            for (int i=1;i<=b;i++)
             s[a+1][i]=-1;  //上面多一格的位置全部复制等于-1，避免越界。
            dfs(1,1);  //从坐标1,1开始深搜。
            cout<<ans<<endl;  //输出方案总数。
        .}

总体来说，这题来说还是十分简单的，可以给刚学搜索的人练一下。希望大家多刷一点题。 #早日成为大牛！！！！