题意就是:
给你一个n*m的矩阵,矩阵中有W(向上),A(向左),S(向下),D(向右)
就是问你有多少个点能做出去(按他给的方向）
解析：
就是反向跑了一个dfs，让最外面的跑如果能跑出去，就反向把他所有的路径都跑出来；
#include<iostream> #include<algorithm> #include<map> #include<string> #include <math.h> #include<bits/stdc++.h> using namespace std; typedef long long ll; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } const int INF=0x3f3f3f3f; const int maxn=1e3+10; char a[maxn][maxn]; int vis1[maxn][maxn]; int vis[maxn][maxn]; int n,m; int ans=0; void dfs(int x,int y){ vis1[x][y]=1; if(x+1>=1&&x+1<=n&&y>=1&&y<=m&&a[x+1][y]=='W'&&vis[x+1][y]==0){ vis[x+1][y]=1; dfs(x+1,y); vis[x+1][y]=0; } if(x-1>=1&&x-1<=n&&y>=1&&y<=m&&a[x-1][y]=='S'&&vis[x-1][y]==0){ vis[x-1][y]=1; dfs(x-1,y); vis[x-1][y]=0; } if(x>=1&&x<=n&&y+1>=1&&y+1<=m&&a[x][y+1]=='A'&&vis[x][y+1]==0){ vis[x][y+1]=1; dfs(x,y+1); vis[x][y+1]=0; } if(x>=1&&x<=n&&y-1>=1&&y-1<=m&&a[x][y-1]=='D'&&vis[x][y-1]==0){ vis[x][y-1]=1; dfs(x,y-1); vis[x][y-1]=0; } } 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<=m;i++){//上 if(a[1][i]=='W'){ vis[1][i]=1; dfs(1,i); vis[1][i]=0; } } for(int i=1;i<=m;i++){//下 if(a[n][i]=='S'){ vis[n][i]=1; dfs(n,i); vis[n][i]=0; } } for(int i=1;i<=n;i++){//左 if(a[i][1]=='A'){ vis[i][1]=1; dfs(i,1); vis[i][1]=0; } } for(int i=1;i<=n;i++){//右 if(a[i][m]=='D'){ vis[i][m]=1; dfs(i,m); vis[i][m]=0; } } int ans=0; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ // cout<<vis1[i][j]<<" "; if(vis1[i][j]==1){ ans++; } } // cout<<endl; } cout<<ans<<endl; }