应该是超时了,递归次数太多了。
by 3_14 @ 2024-04-04 16:54:26
@[张一2010](/user/1038838)
还有MLE,内存爆了,开小一点又RE了,所以要优化代码(简称重写)
by 3_14 @ 2024-04-04 16:56:54
@[张一2010](/user/1038838)
总之,就是递归不行,太多次定义了,所以爆了.
by 3_14 @ 2024-04-04 17:03:37
@[3_14](/user/913288) 为什么这篇 [题解](https://www.luogu.com.cn/article/xw7rchpa) 能过?我的代码和他的有什么区别吗?
(新代码:
```cpp
#include<bits/stdc++.h>
#define itn int
using namespace std;
itn n,m,ans;char Map[1002][1002];
int px(char a){
if(a=='u') return -1;
if(a=='l'||a=='r') return 0;
if(a=='d') return 0;
}
int py(char a){
if(a=='l') return -1;
if(a=='u'||a=='d') return 0;
if(a=='r') return 1;
}
bool dfs(int x,int y){
if(x<1||x>n||y<1||y>m) return 0;
else if(Map[x][y]=='w') return 0;
else if(Map[x][y]=='o'){
return 1;
}
if(dfs(x+px(Map[x][y]),y+py(Map[x][y]))){
Map[x][y]='o';
return 1;
}else{
Map[x][y]='w';
return 0;
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) cin>>Map[i][j];
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int bol=dfs(i,j);
if(bol) ans++;
}
}
cout<<ans;
return 0;
}
```
ans有改动,但仍MLE)
by 张一2010 @ 2024-04-04 21:34:59
@[张一2010](/user/1038838)
不一定,但是(可能)你的递归次数比他多,还是算法问题。...
by 3_14 @ 2024-04-04 21:53:22
@[3_14](/user/913288) 好吧,感谢大佬!
by 张一2010 @ 2024-04-04 21:55:00
@[张一2010](/user/1038838)
你px中
if(a=='d') return 0;
应该是return 1吧
~~xun~~
by Tommyzheng11 @ 2024-04-09 18:19:49
@[张一2010](/user/1038838)
不过还是MLE寄
by Tommyzheng11 @ 2024-04-09 18:20:36
新代码:
```cpp
#include<bits/stdc++.h>
#define itn int
using namespace std;
itn n,m,ans;char Map[1002][1002];//int www;
bool pdmap[1002][1002];
int px(char a){
if(a=='u') return -1;
if(a=='l'||a=='r') return 0;
if(a=='d') return 1;
}
int py(char a){
if(a=='l') return -1;
if(a=='u'||a=='d') return 0;
if(a=='r') return 1;
}
bool dfs(int x,int y/*,int sx,int sy,int d*/){//www++;
// if(x==sx&&y==sy&&d!=0) return 0;
if(pdmap[x][y]==1){
if(Map[x][y]=='w') return 0;
else if(Map[x][y]=='o') return 1;
}
pdmap[x][y]==1;
if(x<1||x>n||y<1||y>m) return 0;
if(dfs(x+px(Map[x][y]),y+py(Map[x][y])/*,sx,sy,d+1*/)){
Map[x][y]='o';
return 1;
}else{
Map[x][y]='w';
return 0;
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) cin>>Map[i][j];
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(dfs(i,j/*,i,j,0*/)) ans++;
}
}
cout<<ans;//cout<<"\n\n\nwww:"<<www;
return 0;
}
```
此篇[题解](https://www.luogu.com.cn/article/vl30trqy)与我的更像,
但我不理解yes[i][j]=3 有什么用?
@[Tommyzheng11](/user/680584)
by 张一2010 @ 2024-04-10 17:39:25
@[Tommyzheng11](/user/680584)
new code:
```cpp
#include<bits/stdc++.h>
#define itn int
using namespace std;
itn n,m,ans;char Map[1002][1002]/*1.u,d,l,r未访问过;2.o可到达;3.w不可到达;4.(important:判断环)n正在访问*/;
int px(char a){
if(a=='u') return -1;
if(a=='l'||a=='r') return 0;
if(a=='d') return 0;
}
int py(char a){
if(a=='l') return -1;
if(a=='u'||a=='d') return 0;
if(a=='r') return 1;
}
bool dfs(int x,int y){
if(x<1||x>n||y<1||y>m) return 0;
//if(Map[x][y]=='w'||Map[x][y]=='n') return 0;
if(Map[x][y]=='w'){
cout<<"w\n";
return 0;
}
if(Map[x][y]=='n'){
cout<<"n\n";
return 0;
}
if(Map[x][y]=='o'){
return 1;
}
Map[x][y]='n';
if(dfs(x+px(Map[x][y]),y+py(Map[x][y]))){
Map[x][y]='o';/*cout<<1<<"\n";
cout<<x<<" "<<y<<"\n";
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++) cout<<Map[i][j]<<" ";
cout<<"\n";
}cout<<"\n";*/
return 1;
}else{
Map[x][y]='w';/*cout<<2<<"\n";
cout<<x<<" "<<y<<"\n";
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++) cout<<Map[i][j]<<" ";
cout<<"\n";
}cout<<"\n";*/
return 0;
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) cin>>Map[i][j];
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(dfs(i,j)) ans++;
}
}
cout<<ans;
/* cout<<"\n\n";
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++) cout<<Map[i][j]<<" ";
cout<<"\n";
}
*/ return 0;
}
```
我把‘正在搜索’这一状态加了,但输出是错的,我不知道哪里错了,求debug
by 张一2010 @ 2024-04-27 17:33:38