不会有环是重点
每一条线的方向唯一确定,会且一定会被走两次(两端开始)
d:方向: 0(向上),1(向右),2(向下),3(向左)
我们注意到一点:
当镜子为’\‘:
向下(2) -》 向右(1)
向右(1) -》 向下(2)
向左(3) -》 向上(0)
向上(0) -》 向左(3)
转化前后为异或3的关系
当镜子为’/’:
向下(2) -》 向左(3)
向右(1) -》 向上(0)
向左(3) -》 向下(2)
向上(0) -》 向右(1)
转化前后为异或1的关系
如果仍然没有弄懂看一看其他两位大佬的细讲
xianhai 的图示异或关系
wanghai673的 复杂度证明
时间复杂度O(NM)
#include<bits/stdc++.h>
using namespace std;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};//分别是:向上,向右,向下,向左
char g[1010][1010];
int ans, n, m;
void dfs(int x, int y, int d, int u){
ans = max(ans, u);
int nd;
if(g[x][y] == '/') nd = d ^ 1;
else nd = d ^ 3;
int nx = x + dx[nd], ny = y + dy[nd];//下一个位置
if(nx && ny && nx <= n && ny <= m)//如果下一个位置依旧在规定位置里
dfs(nx, ny, nd, u + 1);
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
cin >> g[i][j];
for(int i = 1; i <= m; i++){
dfs(1, i, 2, 1);//最上面的一行,入射方向向下
dfs(n, i, 0, 1);//最下面的一行,入射方向向上
}
for(int i = 1; i <= n; i++){
dfs(i, 1, 1, 1);//最左边的一行,入射方向向右
dfs(i, m, 3, 1);//最右边的一行,入射方向向左
}
cout << ans;
return 0;
}
短代码
#include<bits/stdc++.h>
using namespace std;
const int sk = 2010;
char g[4001000];
int ans, n, m, dxy[] = {-sk, 1, sk, -1};//分别是:向下,向右,向上,向左
void dfs(int xy, int d, int u){
ans = max(ans, u);
int nd = d ^ 1 ^ ((g[xy] == '\\') << 1), nxy = xy + dxy[nd];//下一个位置
if(nxy >= 0 && nxy / sk < n && nxy % sk < m) dfs(nxy, nd, u + 1);
}
int main(){
cin >> n >> m;
for(int i = 0; i < n * m; i++) cin >> g[(i / m) * sk + i % m];
for(int i = 0; i < m; i++) dfs(i, 2, 1), dfs((n - 1) * sk + i, 0, 1);
for(int i = 0; i < n; i++) dfs(i * sk, 1, 1), dfs(i * sk + m - 1, 3, 1);
cout << ans;
return 0;
}
为哈在dfs里没用异或用switch语句来条件判断直接就mle了,其他写法都一样,没看哪有多余的内存开销啊
太精悍了吧啊sir
这个偏移量是数组位置偏移量,不要想当然往上走就是x不变y+1,而应该是x-=1,y不变。向上或者向下对应的是行变化,向左或者向右对应的是列变化
异或用得太妙了
拿到题没思路,看题解,发现推理过程十分困难.
偏移量怎么看啊?大佬
你指的是什么偏移量
请问为什么不会有无限循环的情况?
无限循环的话请问你是怎么进去的
光路可逆,无限循环相当于没有入射光了。
你说的无限循环应该是指, 进去后, 一直循环出不来吧? 可以看看y总的视频呀, 因为是环图, 节点的入度只有 2、1、0 均小于等于2 所以只可能有若干条链, 配上若干个简单环,所以不可能会无限循环……
卧槽时间复杂度理解太牛了,%%%
牛子
想问大佬是怎么发现这个方向对应关系是异或关系的呢?
之前写图论题用到了异或1来确定是不是同一条边的来回,这个也差不多就可以想到,然后列举一下,发现是可以的。
异或1判断是否是同一条边的来回这个我知道,但这道题属实没想到能用异或来转化,我很朴素的用了个哈希来对应,dalao tql!
思维发散一点,我是先注意到 (0,1),(2,3)在 \ 的时候是互相达到的,然后 / 的时候通过对立方向是 ^2 达到的,也就是先异或1,再异或2,得到就是异或3,最后再简化一下步骤
代码里的注释貌似打错了,应该是“上,右,下,左”吧。
谢谢,更改了
为什么复杂度不是N^3?dfs复杂度不是n^2的么?orz
每一条光线都是走两次,不会就是每次都是走N * M个点
奥奥 懂了 原来除了起始,不同出发点的路径不相交
每次都是大佬您的题解最早最受欢迎……(好羡慕您飙升的阅读量)
az,为大家服务,感谢大家支持哦
谢谢大佬让我知道这样暴力不会超时(我算出来应该会T……)
刚想问
^1
和^3
是什么知识点,大佬您就发了,感谢