DFS
样例
void dfs(int step)
{
if(边界)//找到解 or 走不下去
{
......
return;
}
for(...)//尝试每一种可能
{
if(ischeck(...)==false)
{
ischeck(...)=true;
dfs(step+1);
}
ischeck(...)=false;//回溯
}
}
struct node
{
int x,y;
}Node;
bool inq[N][N]={false};
int marix[N][N];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>marix[i][j];
bool judge(int x,int y)
{
if(marix[x][y]==1&&inq[x][y]==false) return true;
else return false;
}
int xc[4]={0,0,-1,1};
int yc[4]={-1,1,0,0};
while(x!=4&&y!=3)
{
BFS(x,y);
}
if(judge(i,j)==true)
{
BFS(i,j);
num++;
}
}
int num=0;
void BFS()
{
queue<node>q;
Node.x=2,Node.y=2;
q.push(Node);
while(!q.empty())
{
node* top=q.front();
q.pop();
for(int i=0;i<4;i++)
{
if(judge(top.x+xc[i],top.y+yc[i])==true)
{
Node.x=top.x+xc[i];
Node.y=top.y+yc[i];
q.push(Node);
inq[x][y]=true;
}
}
}
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla