题目描述
分析与思路
将样例转换成箭头如下图,赤裸裸的环,不标记的话稳稳地被T(LE)飞
通过简单的画图发现从边界出口开始反向路径唯一,并且路径转移符合以下规律,当上下左右为SWDA时可以转移到中间的单元格
鉴于这个思想,想了一个p数组与下标dir数组的一维坐标相对应,减少不必要的枚举,39行代码AC
char s[1006][1006],p[5]="AWSD";//与dir数组相对应 int bo[1006][1006],dir[4][2]={0,1,1,0,-1,0,0,-1};
AC代码(附有良心注释)
#include<bits/stdc++.h> using namespace std; char s[1006][1006],p[5]="AWSD";//与dir数组相对应 int bo[1006][1006],dir[4][2]={0,1,1,0,-1,0,0,-1}; int main() { int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;++i) scanf("%s",s[i]+1); int an=0; queue<pair<int,int> >q; for(int i=1;i<=m;++i){//将出口加入队列 if(s[1][i]=='W') q.push(make_pair(1,i)); if(s[n][i]=='S') q.push(make_pair(n,i)); } for(int i=1;i<=n;++i){//将出口加入队列 if(s[i][1]=='A') q.push(make_pair(i,1)); if(s[i][m]=='D') q.push(make_pair(i,m)); } while(!q.empty()){ pair<int,int> no,ne; no=q.front(); q.pop(); bo[no.first][no.second]=1; ++an; for(int i=0;i<4;++i){ ne.first=no.first+dir[i][0],ne.second=no.second+dir[i][1]; if(!bo[ne.first][ne.second]&&s[ne.first][ne.second]==p[i]&&ne.first>=1&&ne.first<=n&&ne.second>=1&&ne.second<=m) q.push(ne); //未被标记,符合转移规律,坐标在范围内 } } printf("%d\n",an); return 0; }