질문 - 일반적인 검색 - DFS 반복

17871 단어 귀속DFS
네 방향, 매번 한 방향을 선택하여 가고, 통하지 않을 때 다음 방향으로 가고, 네 방향이 모두 가지 못할 때 한 칸씩 물러난다.제목에 따라 DFS 재귀화를 사용할 수 있습니다.
#include<stdio.h>
#include<string.h>
int n,m,i,j,k,flag,count;
int data[5][5],vis[5][5]; 
int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
struct Path
{
  int a,b;
}path[10][10];
void dfs(int x,int y)
{
	int i,xx,yy;
	if(x==4&&y==4){
	flag=1;
	return;
	}
  for(i=0;i<4;i++)
  {
    xx = x+dir[i][0];
	yy = y+dir[i][1];
	if(vis[xx][yy]==0&&data[xx][yy]==0&&xx>=0&&xx<5&&yy>=0&&yy<5)
	{
		vis[xx][yy] = 1;
		path[xx][yy].a=x;
		path[xx][yy].b=y;
	    dfs(xx,yy);

		if(flag) return;

		path[xx][yy].a=-1;
		path[xx][yy].b=-1;
		vis[xx][yy]=0;
	}
  }
}
int main()  //  
{
 for(i=0;i<5;i++)
  for(j=0;j<5;j++)
	  scanf("%d",&data[i][j]);
  memset(vis,0,sizeof(vis));
  memset(path,-1,sizeof(path));
  flag=0;
  dfs(0,0);
  for(i=0;i<5;i++)
    for(j=0;j<5;j++)
		if(path[i][j].a!=-1)
		printf("(%d, %d)
",path[i][j].a,path[i][j].b); printf("(4, 4)
"); return 0; }

좋은 웹페이지 즐겨찾기