我是用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; }