比赛 动态规划练习赛1102 评测结果 C
题目名称 激光电话 最终得分 0
用户昵称 小金 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2023-11-02 21:57:03
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
int a[110][110]={},n,m,ans=0x3f3f3f3f,x1=0,x2=0,y1=0,y2=0,dis[4][2]={{-1,0},{1,0},{0,-1},{0,1}},b[110][110]={};
void dfs(int nx,int ny,int d,int s)
{
    if(nx==x2&&ny==y2)
    {
        if(s<ans)
        {
            ans=s;
        }
        return;
    }
    if(nx<1||nx>n||ny<1||ny>m)
    {
        return;
    }
    for(int i=0;i<=3;i++)
    {
        int dx=nx+dis[i][0];
        int dy=ny+dis[i][1];
        if(a[dx][dy]!=1&&b[dx][dy]==0)
        {
            if(i!=d)
            {
                b[dx][dy]=1;
                dfs(dx,dy,i,s+1);
                b[dx][dy]=0;
            }
            else
            {
                b[dx][dy]=1;
                dfs(dx,dy,d,s);
                b[dx][dy]=0;
            }
        }
    }
}
int main()
{
    freopen("lphone.in","r",stdin);
    freopen("lphone.out","w",stdout);
    cin>>m>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            char l;
            cin>>l;
            if(l=='*')
            {
                a[i][j]=1;
            }
            if(l=='C')
            {
                if(x1==0)
                {
                    x1=i;
                    y1=j;
                }
                else
                {
                    x2=i;
                    y2=j;
                }
            }
        }
    }
    b[x1][y1]=1;
    dfs(x1,y1,-1,0);
    cout<<ans-1;
    return 0;
}