CSU1569: Wet Tiles（BFS控制时间相同）(二)

There will be one or more houses in the data file and a line with a single integer -1 designates the end of the data set.

Output

For each house, display the total number of tiles that are wet after T minutes.

Sample Input

12 12 5 3 5
2 11 3 3 9 5
1 9 6 9 1 7 4 4 7 1 7 4
10 9 10 12 11 4 12 4
9 7 8 1 3
4 3
2 2 6 6 6 2 2 6 8 2 8 2
6 7 50 1 3
3 4
2 2 2 6 3 6 5 4 5 4 3 2
12 12 5 3 0
2 11 3 3 9 5
-1

Sample Output

75
17
4
94

HINT

?

Source

#include
  
   
#include
   
     #include
    
      using namespace std; const int N = 1005; struct locate { int x,y; }; int mapt[N][N],n,m,T,dir[4][2]={0,1,0,-1,1,0,-1,0}; queue
     
      q[2]; void bfs(int flag) { locate pre,now; while(!q[flag].empty()) { pre=q[flag].front();q[flag].pop(); for(int e=0;e<4;e++) { now.x=pre.x+dir[e][0]; now.y=pre.y+dir[e][1]; if(now.x>0&&now.x<=n&&now.y>0&&now.y<=m&&mapt[now.x][now.y]==0) { mapt[now.x][now.y]=1; q[!flag].push(now); } } } } int main() { int L,W; locate now,pre; while(scanf("%d",&n)>0&&n!=-1) { scanf("%d%d%d%d",&m,&T,&L,&W); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) mapt[i][j]=0; while(!q[0].empty())q[0].pop(); while(!q[1].empty())q[1].pop(); while(L--) { scanf("%d%d",&now.x,&now.y); q[0].push(now); } while(W--) { scanf("%d%d%d%d",&pre.x,&pre.y,&now.x,&now.y); if(now.x>pre.x) { int tt; tt=pre.x; pre.x=now.x; now.x=tt; tt=pre.y; pre.y=now.y; now.y=tt; } if(pre.x==now.x) { if(pre.y
      
       =now.y) { mapt[pre.x][pre.y--]=2; } } else if(pre.y==now.y) { if(pre.x
       
        =now.x) { mapt[pre.x--][pre.y]=2; } } else if(pre.x>=now.x&&pre.y<=now.y) { while(now.x<=pre.x&&now.y>=pre.y) { mapt[now.x][now.y]=2; now.y--; now.x++; } } else { while(now.x<=pre.x&&now.y<=pre.y) { mapt[pre.x][pre.y]=2; pre.y--; pre.x--; } } } int flag=0; while(!q[flag].empty()) {T--; if(T==0) break; bfs(flag); flag=!flag; } int ans=0; for(int j=m;j>=1;j--) { for(int i=1;i<=n;i++) { //printf("%d ",mapt[i][j]); if(mapt[i][j]==1) ans++; } //printf("\n"); } printf("%d\n",ans); } }