一个简单的dfs问题求大佬指点一下
题目描述给你row*col的数字矩形(1-9组成),最开始你在左上角,你可以上下左右移动,
已经移动过的数字不可以再向该位置移动了。请问你最多可以经过多少个不同的数字?
4 5
11111
22112
11313
11111
只能向下走,而且只能走一步, 所以输出2
输入
每次输入都是单个数据,先给 row,col ,再给row*col大小的矩形。
col,row<100
输出
请问你最多可以经过多少个不同的数字?
样例输入
4 5
1 1 1 1 1
2 2 1 1 2
1 1 3 1 3
1 1 1 1 1
样例输出
2
再贴一下自己写的垃圾代码
#include<iostream>
#include<algorithm>
#include<string.h>
#include<string>
using namespace std;
int m,n,a[100][100],vis[100],num=0;
int check(int m,int k)
{
int w=0;
for(int i=0;i<100;i++)
{
if(vis[i]==m)
{
w=1;
}
}
if(w==1)
return 0;
else
{
vis[++k]=m;
return 1;
}
}
void dfs(int l,int r)
{
int dir[4][2]={0,1,1,0,0,-1,-1,0};
for(int i=0;i<4;i++)
{
int ll=l+dir[i][0];
int rr=r+dir[i][1];
if(ll>=0&&ll<n&&rr>=0&&rr<m&&check(a[ll][rr],num))
{
++num;
dfs(ll,rr);
}
}
}
int main()
{
memset(vis,0x3f,sizeof(vis));
cin>>n>>m;
for(int i=0;i<n;i++)
for(int j=0;i<m;j++)
cin>>a[i][j];
vis[0]=a[0][0];//去你妈的 fuck!!!
dfs(0,0);
cout<<num<<endl;
return 0;
}
求指教!!!