巡检

思路与复杂度

用方向数组表示北东南西，左右转向以模4更新；前进前检查边界与障碍。用布尔数组记录访问格，初始格也计数。时间 O(nm+k)，空间 O(nm)。

正确性与边界

模拟状态与每一步指令后的真实位置方向一致，访问数组只在首次进入时增加计数。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n,m;cin>>n>>m;vector<string>a(n);for(auto&s:a)cin>>s;int x,y,d,k;cin>>x>>y>>d>>k;--x;--y;string op;cin>>op;int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};vector<unsigned char>v(n*m);v[x*m+y]=1;int cnt=1;for(char c:op){if(c=='L')d=(d+3)%4;else if(c=='R')d=(d+1)%4;else{int nx=x+dx[d],ny=y+dy[d];if(nx>=0&&nx<n&&ny>=0&&ny<m&&a[nx][ny]!='#'){x=nx;y=ny;if(!v[x*m+y])v[x*m+y]=1,++cnt;}}}cout<<x+1<<" "<<y+1<<" "<<d<<" "<<cnt<<"\n";}