解题思路:
首先,处理11种不同的水管,分4个方向,1表示有接口,0表示没有接口。用一个二维数组存所有种类的水管。
然后,把输入的字符转化成数字,可以再输入的时候边输入边处理,用字符减去字符“A”就可以了,对应的上面给11中不同水管中的一种。
深搜的时候,如果访问到某个方格时,先判断它是否被访问过,然后立刻标记为已访问。然后就是判断当前方格的四个方向是不是有接口,如果某个方向有接口的话,就判断这个方向上的下一个方格中,和当前方格相邻的边是不是有接口,如果有接口,则继续深搜这个相邻的点。这里有个处理:(i+2)%4,意味着,比如:当前方格如果右边有接口,则判断右边的方格的左边的边是不是有接口,其它情况一样。
//zoj 2412 #include <iostream> #include <cstring> using namespace std; const int SIZE=55; int a[SIZE][SIZE], vis[SIZE][SIZE]; int M, N, sum; //up, right, down, left int sg[11][4]={{1,0,0,1},{1,1,0,0},{0,0,1,1},{0,1,1,0}, {1,0,1,0},{0,1,0,1},{1,1,0,1},{1,0,1,1}, {0,1,1,1},{1,1,1,0},{1,1,1,1}}; int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}}; void dfs(int x, int y) { int tx, ty, t0, t1; vis[x][y]=1; t0=a[x][y]; for(int i=0;i<4;i++) { tx=x+dir[i][0]; ty=y+dir[i][1]; if(tx<0 || tx>=M || ty<0 || ty>=N || vis[tx][ty]) continue; t1=a[tx][ty]; if(sg[t0][i] && sg[t1][(i+2)%4]) dfs(tx,ty); } } int main() { char ch; while(1) { cin>>M>>N; if(M<0 || N<0) break; for(int i=0;i<M;i++) for(int j=0;j<N;j++) {cin>>ch; a[i][j]=ch-'A';} memset(vis,0,sizeof(vis)); sum=0; for(int i=0;i<M;i++) for(int j=0;j<N;j++) if(!vis[i][j]) { dfs(i,j); sum++; } cout<<sum<<endl; } return 0; }