P8462 「REOI-1」奶油蛋糕

简单的dfs，我直接上代码了。

#include <iostream>
#include <cstring>
using namespace std;
int maze[51][51];
int len[51][51];
int temp[51][51][1001];            /*(x,y)坐标走过的记录，例如（1,1,1)代表(1,1)走第一次的记录*/
int n,m,x,y;
string s;
bool in(int x,int y)
{
    return x>=1&&x<=n&&y>=1&&y<=n;
}
void dfs(int x,int y,int index1)             /*dfs暴力搜*/
{
    if(index1>=m+1)
    {
        return;
    }
    len[x][y]++;
    temp[x][y][len[x][y]]=index1;
    if(s[index1]=='N')
    {
        int ty=y+1;
        int tx=x;
        if(in(tx,ty))
        {
            dfs(tx,ty,index1+1);
        }
    }
    if(s[index1]=='S')
    {
        int ty=y-1;
        int tx=x;
        if(in(tx,ty))
        {
            dfs(tx,ty,index1+1);
        }
    }
    if(s[index1]=='W')
    {
        int ty=y;
        int tx=x-1;
        if(in(tx,ty))
        {
            dfs(tx,ty,index1+1);
        }
    }
    if(s[index1]=='E')
    {
        int ty=y;
        int tx=x+1;
        if(in(tx,ty))
        {
            dfs(tx,ty,index1+1);
        }
    }
}
int main()
{
    cin>>n>>m>>x>>y;
    cin>>s;
    memset(temp,-1,sizeof(temp));
    dfs(x,y,0);                                      /*x坐标和y坐标与题意一样*/
    long long sum=0;
    int t=1;
    for(int i=1;i<=m;i++)
    {
        sum=sum+i;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            len[j][n-i+1]++;                             /*最后一个坐标设为m*/
            temp[j][n-i+1][len[j][n-i+1]]=m;
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            for(int k=0;k<len[j][n-i+1];k++)                                 /*每个坐标我们走过了几次*/
            {
                t=0;                                                         
                for(int l=temp[j][n-i+1][k]+1;l<temp[j][n-i+1][k+1];l++)     /*每个区间阶段求和*/
                {
                    ++t; 
                    maze[j][n-i+1]=maze[j][n-i+1]+t;                         /*0-m进行求和*/
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cout<<maze[j][n-i+1]<<" ";
        }
        cout<<endl;
    }
    return 0;
}