pastebin

Paste Search Dynamic
Recent pastes
bfs
  1. #include<cstdio>
  2. #include<cstring>
  3. #include<iostream>
  4. using namespace std;
  5. const int wx[4]={0,0,1,-1},wy[4]={1,-1,0,0};
  6. int n,m;
  7. bool map[21][21];
  8. bool walk[21][21];
  9. int max(int a,int b)
  10. {
  11.     if(a>b) return a;
  12.     return b;
  13. }
  14. struct Node {
  15.     int x,y,deep;
  16. }q[100000];
  17. int bfs(int x,int y)
  18. {
  19.     memset(walk,0,sizeof(walk));
  20.     q[1].x=x,q[1].y=y,q[1].deep=0;
  21.     walk[x][y]=1;
  22.     int l=1,r=1;
  23.     while(l<=r)
  24.     {
  25.         for(int i=0;i<4;++i)
  26.         {
  27.             int tx=q[l].x+wx[i],ty=q[l].y+wy[i];
  28.             if(map[tx][ty]==1||walk[tx][ty]==1||tx<=0||ty<=0||tx>n||ty>m) continue;
  29.             q[++r].x=tx,q[r].y=ty;
  30.             q[r].deep=q[l].deep+1;
  31.             walk[tx][ty]=1;
  32.         }
  33.         ++l;
  34.     }
  35.     for(int i=1;i<=r;++i)
  36.     {
  37.         printf("%d %d %d\n",q[i].x,q[i].y,q[i].deep);
  38.     }
  39.     return q[r].deep;
  40. }
  41. int main()
  42. {
  43.     scanf("%d%d",&n,&m);
  44.     char ch;
  45.     for(int i=1;i<=n;++i)
  46.     {
  47.         for(int j=1;j<=m;++j)
  48.         {
  49.             cin>>ch;
  50.             if(ch=='#') map[i][j]=1;
  51.         }
  52.     }
  53.     int ans=0;
  54.     /*for(int i=1;i<=n;++i)
  55.     {
  56.         for(int j=1;j<=m;++j)
  57.         {
  58.             if(map[i][j]==0) ans=max(ans,bfs(i,j));
  59.         }
  60.     }*/
  61.     printf("%d",bfs(1,5));
  62. }
Parsed in 0.010 seconds