某天,本蒟蒻打开洛谷想刷几个水题找找自信,于是打开了此题, 洛谷 P1605 迷宫
当时内心os:诶呀这数据可真小啊,不就是dfs入门嘛,看我5分钟AC,这水题真没意思...
于是飞速打出“完美”的代码:

#include <bits/stdc++.h>
using namespace std;
int n,m,xx,yy,t,newx,newy,beginx,beginy,endx,endy,sum=0,a[6][6];//a数组初始化是0
int dir[4][2]={{0,-1},{0,1},{-1,0},{1,0}};
void dfs(int x,int y)
{
    if(x==endx&&y==endy){sum++;return;}
    a[x][y]=1;
    for(int i=0;i<4;i++)
    {
        newx=x+dir[i][0];
        newy=y+dir[i][1];
        if(newx>=1&&newx<=n&&newy>=1&&newy<=m&&a[newx][newy]==0)
        dfs(newx,newy);
    }
}
int main()
{
    cin>>n>>m>>t>>beginx>>beginy>>endx>>endy;
    while(t--)
    {
        cin>>xx>>yy;
        a[xx][yy]=1;
    }
    dfs(beginx,beginy);
    printf("%d\n",sum);
    return 0;
}

然后自信满满地提交:竟然WA了5个点???
在这里插入图片描述

后来我翻了十几篇洛谷大佬们写的题解,终于发现原来我少了一行回溯的过程,
在dfs函数的最后加上a[x][y]=0终于AC了(啊我死了)

//AC代码
#include <bits/stdc++.h>
using namespace std;
int n,m,xx,yy,t,newx,newy,beginx,beginy,endx,endy,sum=0,a[6][6];//a数组初始化是0
int dir[4][2]={{0,-1},{0,1},{-1,0},{1,0}};
void dfs(int x,int y)
{
    if(x==endx&&y==endy){sum++;return;}
    a[x][y]=1;
    for(int i=0;i<4;i++)
    {
        newx=x+dir[i][0];
        newy=y+dir[i][1];
        if(newx>=1&&newx<=n&&newy>=1&&newy<=m&&a[newx][newy]==0)
        dfs(newx,newy);
    }
    a[x][y]=0;//这句话非常非常关键!!!一定要回溯!
    //注意每次设完障碍物都要还原因为地图是全局的,现在不能走,不代表回溯之后的其他路也不能走!
}
int main()
{
    cin>>n>>m>>t>>beginx>>beginy>>endx>>endy;
    while(t--)
    {
        cin>>xx>>yy;
        a[xx][yy]=1;
    }
    dfs(beginx,beginy);
    printf("%d\n",sum);
    return 0;
}

嗯,今天学校停电,学校的OJ也上不去了,图书馆的Wifi还是一如既往地慢出天际,OJ的水题也不会做,只能做做洛谷的模板题才能够维持得了生活这样子,洛谷里面个个都是人才,说话又好听,每次上洛谷就和回到家一样,诶哟超喜欢这里的!(自动脑补窃格瓦拉ing)