首页 > 代码库 > 水管bfs 完成版

水管bfs 完成版

#include<iostream>
int data[50][50]={0};
int visit[50][50]={0};
int hang,lie,num;
int k=0;
int x,y;
int connectto[7][4]={1,1,1,1,
                     1,0,1,0,
                     0,1,0,1,
                     1,1,0,0,
                     0,1,1,0,
                     0,0,1,1,
                     1,0,0,1};
int beconnected[7][4]={1,1,1,1,
                       1,0,1,0,
                       0,1,0,1,
                       0,0,1,1,
                       1,0,0,1,
                       1,1,0,0,
                       0,1,1,0};
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int flag=0;
//void dfs(int x,int y,int step)
//{     
//	 
//	if(step==num)
//	{
//        return;
//	}
//	for(int i=0;i<4;i++)
//	{
//		int nx=x+dx[i];
//		int ny=y+dy[i];
//		int a=data[x][y]-1;
//		int b=data[nx][ny]-1;
//		
//		if(nx>=0&&nx<hang&&ny>=0&&ny<lie&&connectto[a][i]&&beconnected[b][i]&&b!=-1&&visit[nx][ny]!=1)
//		{
//			visit[nx][ny]=1;
//			dfs(nx,ny,step+1);
//		}
//	}
//
//}
//int main()
//{     
//	 freopen("input.txt","r",stdin);
//	 scanf("%d%d%d",&hang,&lie,&num);
//	 scanf("%d%d",&x,&y);
//	 for(int i=0;i<hang;i++)
//		{for(int j=0;j<lie;j++)
//			scanf("%d",&data[i][j]);
//	     }
//	 for(int i=0;i<hang;i++)
//		{for(int j=0;j<lie;j++)
//			printf("%d",data[i][j]);
//	       printf("\n");
//	     }
//	 printf("\n");
//	 //data[x][y]=9;
//	 visit[x][y]=1;
//	 dfs(x,y,0);
//	 
//	  for(int i=0;i<hang;i++)
//		{for(int j=0;j<lie;j++)
//			printf("%d",visit[i][j]);
//	       printf("\n");
//	     }
//	 printf("\n");
//	 
//	for(int i=0;i<hang;i++)
//		{  for(int j=0;j<lie;j++)
//	        {   if(visit[i][j]==1)
//	           {    
//				   k++;
//	           }
//
//	        }
//
//	    }
//			
//	printf("%d",k);
//
//
//}
typedef struct node
{
	int x;
	int y;
	int step;

}node;
node point[1000000];
void bfs(int x,int y)
{
	int tou=0;
	int wei=1;
	visit[x][y]=1;
	point[tou].x=x;
	point[tou].y=y;
	point[tou].step=0;
	while(tou<wei)
	{ 
		if(flag)
		{
			break;
		}
	 for(int i=0;i<4;i++)
	 {
		int a=data[point[tou].x][point[tou].y]-1;
		int nx=point[tou].x+dx[i];
		int ny=point[tou].y+dy[i];
		int b=data[nx][ny]-1;

		if(nx>=0&&nx<hang&&ny>=0&&ny<lie&&connectto[a][i]==1&&beconnected[b][i]==1&&visit[nx][ny]!=1&&b!=-1)
		{   
			point[wei].step=point[tou].step+1;
			if(point[wei].step>num)
			{
				flag=1;
				break;
			}
			visit[nx][ny]=1;
			point[wei].x=nx;
			point[wei].y=ny;
			wei++;
		}
	 }
	 tou++;
	}

}
int main()
{     
	
	 freopen("input.txt","r",stdin);
	 scanf("%d%d%d",&hang,&lie,&num);
	 scanf("%d%d",&x,&y);
	
	 for(int i=0;i<hang;i++)
		{for(int j=0;j<lie;j++)
			scanf("%d",&data[i][j]);
	     }
	 //visit[x][y]=1;
	bfs(x,y);
	for(int i=0;i<hang;i++) 
		{for(int j=0;j<lie;j++)
			printf("%d",visit[i][j]);
	        printf("\n");
	    }
	  
	for(int i=0;i<hang;i++)
		{  for(int j=0;j<lie;j++)
	        {   if(visit[i][j]>0&&visit[i][j]<=num)
	           {    
				   k++;
	           }

	        }

	    }		
	printf("%d",k);


}

 

水管bfs 完成版