P11228 地图探险 题解

xiaogu111 · 2024-10-26 21:21:56 · 题解

P11228 地图探险 题解

题目链接

题目分析

这道题难度不是很大。

一看题目的描述，我们首先会想到dfs。

但是仔细阅读之后，我们会发现这道题路径唯一，只需简单按照题意模拟即可。

注意：

• 如果你用了一个数组来标记这个点是否走到过，来最后遍历这个数组来求答案，别忘了多测清空。
• 别忘了加上初始点的 1 个经过点。
• 不要每成功移动一次就把计数器自增 1，因为有的点可能会重复走到。

• 数组大小要开够，变量名尽量别用题目里的x0和y0,防止开了万能头之后爆零

  前两道题都没涉及到算法，太舒服了

至于剩下的细节，都在我的代码里，可以自己来看。

代码

#include<iostream>
#include<cstring>
using namespace std;
int t;
char a[1005][1005];
int vis[1005][1005];
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};  //方向数组有序，对应d取1~4，一定要注意
int cnt(int n,int m)  //算经过了几个点
{
    int ans=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(vis[i][j]==1)
                ans++;
    return ans;
}
int main()
{
    cin>>t;
    while(t--)
    {
        memset(vis,0,sizeof(vis));
        int n,m,k,x,y,d;
        cin>>n>>m>>k>>x>>y>>d;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++) 
                cin>>a[i][j];
        vis[x][y]=1;
        for(int i=1;i<=k;i++)
        {
            int nx=x+dx[d],ny=y+dy[d];
            if(nx>=1&&nx<=n&&ny>=1&&ny<=m)  //不越界
            {
                if(a[nx][ny]=='.')  //是空地
                {
                    x=nx;  //走
                    y=ny;
                    vis[x][y]=1;  //别忘标记走过
                    continue;
                }
                else  //向右转
                {
                    d++;     
                    d%=4;    
                    continue;
                }
            } 
            else  //向右转
            {
                d++;
                d%=4;
                continue;
            }
        }   
        cout<<cnt(n,m)<<endl;
    }
    return 0;
}
//code by mht

附

祝愿大家在 CSP-J 中都取得满意的成绩！

rp++;