首页 > 代码库 > 水管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 完成版
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。