[数据结构与算法] ACwing(春季每日一题题解)

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> ACwing(春季每日一题题解) -> 正文阅读

[数据结构与算法]ACwing(春季每日一题题解)

文章目录

- 镜子田地(找规律+dfs)

镜子田地(找规律+dfs)

在这里插入图片描述

题目分析：镜子有两种放置方式 ‘/’ 和 ‘\’

将被镜子分为的上下看做两个节点，根据光路的可逆性，可以得出，每个节点的度数最大为2，故不会在外部射入到内部然后内部出现环，我们需要去枚举光路，因为保证光路是垂直射入，所以如图枚举
在这里插入图片描述
我们需要标记每一步的方向，因为镜子的存在会导致我们下一步的方向是会发生改变的，要根据遇到的镜子分析
1.遇到 ‘ / ’

2.遇到 ‘ \ ’

详细看代码

#include<bits/stdc++.h>
#define ll long long
#define PI 3.141592653589793
#define E 2.718281828459045
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
#define mem(a,b) memset(a,b,sizeof(a))
#define FOR( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define FO( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define lowbit(a) ((a)&-(a))
#define PII pair<ll ,ll >
#define ft first
#define sd second
typedef unsigned long long ull;
const ll mod=10007;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll Max=1e3+10;
using namespace std;
ll t,n,m,l,k;
ll ans;
char mp[Max][Max];
ll mov[][2]={-1,0,0,1,1,0,0,-1};
/*queue<ll> q;
stack<ll> s;
//升序队列
priority_queue <int,vector<int>,greater<int> > q;
//降序队列
priority_queue <int,vector<int>,less<int> >q;*/
ll dfs(ll x,ll y,ll d)
{
    if(x<1||x>n||y<1||y>m)return 0;
    if(mp[x][y]=='/')d^=1;
    else d^=3;
    return dfs(x+mov[d][0],y+mov[d][1],d)+1;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(ll i=1;i<=n;i++)
        for(ll j=1;j<=m;j++)
        cin>>mp[i][j];
    for(ll i=1;i<=n;i++)
    {
        ans=max(ans,dfs(i,1,1));
        ans=max(ans,dfs(i,m,3));
    }
        for(ll i=1;i<=m;i++)
    {
        ans=max(ans,dfs(1,i,2));
        ans=max(ans,dfs(n,i,0));
    }
    cout<<ans<<endl;
    return 0;
}