心得：题目第一眼看过去是简单的dfs，爬行的方向在正常情况下不变，若欲爬行方向，遇到边界和障碍转向，遇到爬过的地方停止，一开始else后面一直sf，后面发现是if里面写乱了，调试后第一个样例能过，卡在答案16那里，我答案是14，在使用下面那行代码由14向1不断找的过程中，发现dx，dy数组设置错误，原因是没有正确设置代表上下左右四个方向的值，例如，i+1，j+0我以为是向右，实际表示的应该是向下，所以调整dx，dy数组后ac了，以后做图的问题方向一定不能搞错。

耗时两个小时

题目描述

蜗牛莎莉喜欢在一个 N×N
的方格矩阵中散步。

她每次都从左上角出发。

方格矩阵中有空地（用 “.” 表示）和障碍（用 “#” 表示）。

下面是一个具体示例：

      A B C D E F G H
    1 S . . . . . # .
    2 . . . . # . . .
    3 . . . . . . . .
    4 . . . . . . . .
    5 . . . . . # . .
    6 # . . . . . . .
    7 . . . . . . . .
    8 . . . . . . . .

莎莉只能沿着水平或垂直方向移动。

在开始时，她位于 A1
位置，并选择一个方向（向下或向右）开始移动。

她会一直沿着一个方向移动，直到遇到矩阵边缘或障碍。

这时，她将转向 90
度，继续前进。

她在移动过程中，不能走出矩阵，或走进有障碍的格子中，也不能走到之前走过的格子中。

当她无法进行任何移动时，行动结束。

以下是上述示例中莎莉的一种行走情况：

      A B C D E F G H
    1 S---------+ # .
    2 . . . . # | . .
    3 . . . . . | . .
    4 . . . . . +---+
    5 . . . . . # . |
    6 # . . . . . . |
    7 +-----------+ |
    8 +-------------+

莎莉沿着右，下，右，下，左，上，右的方向走到了 G7
的位置，此时她无法进行任何移动，行动停止。（前方是她走过的格子，不能进入，并且由于前方不是障碍且没有出界所以也不能转向）

给定具体的方格矩阵，请你帮莎莉找到一个最合理的行进路线，使得她可以经过的格子数量尽可能大。

输出可经过格子最大数量。

样例

输入：8 4
      E2
      A6
      G1
      F5
输出：33

算法1
dfs $O(n^2)$

#include<iostream>
#include<cstring>

using namespace std;
const int N=150;
int a[N][N];
int n,m,res,cnt=1;
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};


void dfs(int i,int j,int k)
{
    res=max(res,cnt);
    //  if(cnt==3) cout<<i<<' '<<j<<' ';//本行确认总数为x的点是多少
    int u=i+dx[k],v=j+dy[k];
    if(a[u][v]==1) return;
    else if(u==0||u>n||v==0||v>n||a[u][v]==2)
    {
        for(int t=k+1;t<=k+3;t+=2)
        {
            int t1=t%4;
            int x=i+dx[t1],y=j+dy[t1];
            if(x>0&&x<=n&&y>0&&y<=n&&a[x][y]==0)
            {
                cnt++;
                a[x][y]=1;
                dfs(x,y,t1);
                cnt--;
                a[x][y]=0;
            }
        }
    }
    else
    {
        cnt++;
        a[u][v]=1;
        dfs(u,v,k);
        cnt--;
        a[u][v]=0;
    }

}

int main()
{
    cin>>n>>m;
    for(int i=0;i<m;i++) 
    {
        int x;
        char y;
        cin>>y>>x;
        y=y-'A'+1;
        a[x][y]=2;
    }


    a[1][1]=1;

    dfs(1,1,0);
    dfs(1,1,1);
    cout<<res;
    return 0;
}