贪吃蛇迷宫!help!!!

常规
1

image
WA45:
#include <bits/stdc++.h>
using namespace std;

const string s = “snuke”;
int n,m,nn,nm;
char a[505][505];
bool flag = true;
bool vis[505][505] = {0};
int x[4] = {1,0,0,-1},y[4] = {0,1,-1,0};

void dfs(int h,int l,int deep)
{
vis[h][l] = true;
if(flag == 0)
return;
if(a[h][l]!=s[deep%5])
return ;
if(h==n && l==m)
flag = 0;
for(int i = 0;i < 4;i++)
{
int nx = h+x[i],ny = l+y[i];
if(vis[nx][ny]==false&&nx>0&&nx<=n&&ny>0&&ny<=m)
{
dfs(nx,ny,deep+1);
}
if(flag == 0)
return;
}
}

int main()
{
cin>>n>>m;
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
cin>>a[i][j];
dfs(1,1,0);
if(flag)
cout<<“No”;
else
cout<<“Yes”;
return 0;
}

TLE75:
#include <bits/stdc++.h>
using namespace std;

const string s = “snuke”;
int n,m,nn,nm;
char a[1005][1005];
bool flag = true;
bool vis[1005][1005] = {0};
int x[4] = {1,-1,0,0},y[4] = {0,0,1,-1};

void dfs(int h,int l,int deep)
{
if(flag == 0)
return;
if(a[h][l]!=s[deep%5])
return ;
if(h==n && l==m)
flag = 0;
for(int i = 0;i < 4;i++)
{
int nx = h+x[i],ny = l+y[i];
if(vis[nx][ny]==false&&nx>0&&nx<=n&&ny>0&&ny<=m)
{
vis[nx][ny] = true;
dfs(nx,ny,deep+1);
vis[nx][ny] = false;
}
if(flag == 0)
return;
}
}
int main()
{
cin>>n>>m;
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
cin>>a[i][j];
vis[1][1] = true;
dfs(1,1,0);
if(flag)
cout<<“No”;
else
cout<<“Yes”;
return 0;
}

I need a big old

2

我来也！！

3 
void dfs(int h,int l,int deep) {
	if(flag == 0)
		return;
	if(a[h][l]!=s[deep%5])
		return ;
	if(h==n && l==m)
		flag = 0;//这里要return
	for(int i = 0; i < 4; i++) {
		int nx = h+x[i],ny = l+y[i];
		if(vis[nx][ny]==false&&nx>0&&nx<=n&&ny>0&&ny<=m) {
			vis[nx][ny] = true;
			dfs(nx,ny,deep+1);
			vis[nx][ny] = false;//不用回溯
		}
		if(flag == 0)//外面有了，重复了，删了
			return;
	}
}
4

@王皓宇 @王皓宇

5

Time Limit Exceeded : 30 分

#include <bits/stdc++.h>
using namespace std;

const string s = “snuke”;
int n,m,nn,nm;
char a[1005][1005];
bool flag = true;
int x[4] = {1,-1,0,0},y[4] = {0,0,1,-1};

void dfs(int h,int l,int deep) {
if(flag == 0)
return;
if(a[h][l]!=s[deep%5])
return ;
if(h==n && l==m)
{
flag = 0;
return;
}
for(int i = 0; i < 4; i++)
{
int nx = h+x[i],ny = l+y[i];
if(nx>0&&nx<=n&&ny>0&&ny<=m)
{
dfs(nx,ny,deep+1);
}
}
}

int main()
{
cin>>n>>m;
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
cin>>a[i][j];
dfs(1,1,0);
if(flag)
cout<<“No”;
else
cout<<“Yes”;
return 0;
}

6

请使用
image
将代码格式化

7

我是说不用回溯了！！不是不用加vis

#include <bits/stdc++.h>
using namespace std;

const string s = "snuke";
int n,m,nn,nm;
char a[1005][1005];
bool flag = true;
int x[4] = {1,-1,0,0},y[4] = {0,0,1,-1};

void dfs(int h,int l,int deep) {
	if(flag == 0)
		return;
	if(a[h][l]!=s[deep%5])//这个东西放到循环里面，就不用再调用一次了
		return ;
	if(h==n && l==m) {
		flag = 0;
		return;
	}
	for(int i = 0; i < 4; i++) {
		int nx = h+x[i],ny = l+y[i];
		if(nx>0&&nx<=n&&ny>0&&ny<=m) {//加vis判断
//vis更新
			dfs(nx,ny,deep+1);
		}
	}
}

int main() {
	cin>>n>>m;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			cin>>a[i][j];
	dfs(1,1,0);//起点vis更新
	if(flag)
		cout<<"No";
	else
		cout<<"Yes";
	return 0;
}
8

@王皓宇 @王皓宇 @王皓宇 @王皓宇

9

栓 Q

10

@CZF2919 AC代码？