Farm Irrigation
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 4498 Accepted Submission(s): 1951
which is marked from A to K, as Figure 1 shows.
Benny has a map of his farm, which is an array of marks denoting the distribution of water pipes over the whole farm. For example, if he has a map
ADC
FJK
IHE
then the water pipes are distributed like
Several wellsprings are found in the center of some squares, so water can flow along the pipes from one square to another. If water flow crosses one square, the whole farm land in this square is irrigated and will have a good harvest in autumn.
Now Benny wants to know at least how many wellsprings should be found to have the whole farm land irrigated. Can you help him?
Note: In the above example, at least 3 wellsprings are needed, as those red points in Figure 2 show.
corresponding square. A negative M or N denotes the end of input, else you can assume 1 <= M, N <= 50.
#include<stdio.h> #include<string.h> #define MAX 55 char map[MAX][MAX]; int ac[MAX][MAX]; int dr[4]={-1,1,0,0}; int dc[4]={0,0,-1,1}; int N,M; int ans; int inmap(int x,int y) { if(x<0||y<0||x>=N||y>=M) return 0; return 1; } int cango(int now_x,int now_y,int dirct) { int x,y; char ch=map[now_x][now_y]; char next; x=now_x+dr[dirct]; y=now_y+dc[dirct]; next=map[x][y]; if(dirct==0) { if(ch=='C'||ch=='D'||ch=='F'||ch=='I') return 0; if(next=='A'||next=='B'||next=='F'||next=='G') return 0; else return 1; } else if(dirct==1) { if(ch=='A'||ch=='B'||ch=='F'||ch=='G') return 0; if(next=='C'||next=='D'||next=='F'||next=='I') return 0; else return 1; } else if(dirct==2) { if(ch=='B'||ch=='D'||ch=='E'||ch=='J') return 0; if(next=='A'||next=='C'||next=='E'||next=='H') return 0; else return 1; } else if(dirct==3) { if(ch=='A'||ch=='C'||ch=='E'||ch=='H') return 0; if(next=='B'||next=='D'||next=='E'||next=='J') return 0; else return 1; } } int dfs(int now_x,int now_y) { int i; if(map[now_x][now_y]=='*') return 0; for(i=0;i<4;i++) { int x=now_x+dr[i]; int y=now_y+dc[i]; if(!inmap(x,y)||map[x][y]=='*'||ac[x][y]==1) continue; if(!cango(now_x,now_y,i)) continue; ac[now_x][now_y]=1; dfs(x,y); ac[now_x][now_y]=0; } map[now_x][now_y]='*'; return 1; } int main() { scanf("%d%d",&N,&M); while(scanf("%d%d",&N,&M),N>=0&&M>=0) { int i,j; ans=0; memset(ac,0,sizeof(ac)); for(i=0;i<N;i++) scanf("%s",map[i]); for(i=0;i<N;i++) for(j=0;j<M;j++) ans+=dfs(i,j); printf("%d\n",ans); } return 0; }