我是用DFS做的这道题，里面有很多细节记录一下。

试题链接：https://ac.nowcoder.com/acm/contest/7501/I

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
typedef long long ll;
using namespace std;
char a[1005][1005];
/*
 W : 上 x-1
 A : 左 y-1
 S : 下 x+1
 D : 右 y+1
 */
int n,m;
int b[1005][1005]; //1/-1
int flag; //flag==1 可以出去，flag==-1 不可以出去
int bianli[1005][1005];
void DFS(int x,int y)
{
    /*一开始的两步非常重要，当遇到已经不能出去，或者可以出去的点，直接判断遇到这个点的上面所有点跟这个点一样就可以*/
    if(b[x][y]==-1)
    {
        flag=-1;
        return;
    }
    if(b[x][y]==1)
    {
        flag=1;
        return;
    }
    /*如果可以出去，则将flag设为1*/
    if(x>n || x<=0 || y>m || y<=0)
    {
        flag=1;
        return;
    }

    /*在遍历之前先看看这个点有没有遍历两遍，如果已经遍历了两遍，则说明成环了，不能出去，flag=-1*/
    bianli[x][y]++;
    if(bianli[x][y]==2)
    {
        flag=-1;
        b[x][y]=-1;
        return;
    }

    if(a[x][y]=='W') DFS(x-1,y);
    if(a[x][y]=='A') DFS(x,y-1);
    if(a[x][y]=='S') DFS(x+1,y);
    if(a[x][y]=='D') DFS(x,y+1);

    /*要么可以出去，要么出不去，最后的flag可能是其中之一*/
    if(flag==1)
    {
        b[x][y]=1;
        return;
    }
    if(flag==-1)
    {
        b[x][y]=-1;
        return;
    }
}
int main()
{

    cin >> n >> m;

    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=m;j++)
        {
            cin >> a[i][j];
        }
    }

    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=m;j++)
        {
            flag=0;
            if(b[i][j]==0) DFS(i,j);
        }
    }
    ll ans = 0;
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=m;j++)
        {
            if(b[i][j]==1) ans++;
        }
    }
    cout << ans << endl;
    return 0;
}