HDU Farm Irrigation 1198
简单深搜,注意如何判断两个方块是否相通
#include <iostream> using namespace std; #define TOLEFT(T) ((T) == 'A' || (T) == 'C' || (T) == 'F' || (T) == 'G' || (T) == 'H' || (T) == 'I' || (T) == 'K') #define TORIGHT(T) ((T) == 'B' || (T) == 'D' || (T) == 'F' || (T) == 'G' || (T) == 'I' || (T) == 'J' || (T) == 'K') #define TOUP(T) ((T) == 'A' || (T) == 'B' || (T) == 'E' || (T) == 'G' || (T) == 'H' || (T) == 'J' || (T) == 'K') #define TODOWN(T) ((T) == 'C' || (T) == 'D' || (T) == 'E' || (T) == 'H' || (T) == 'I' || (T) == 'J' || (T) == 'K') int h, w; char mp[60][60]; int v[60][60]; const int dh[] = {-1, 0, 1, 0}; const int dw[] = {0, 1, 0, -1}; const int ZONG = 0; const int HENG = 1; bool isConnect(int h1, int w1, int h2, int w2, int dir) { if(dir == HENG) { if(w1 > w2) { swap(h1, h2); swap(w1, w2); } return TORIGHT(mp[h1][w1]) && TOLEFT(mp[h2][w2]); } else { if(h1 > h2) { swap(h1, h2); swap(w1, w2); } return TODOWN(mp[h1][w1]) && TOUP(mp[h2][w2]); } } void dfs(int i, int j) { v[i][j] = 1; int th, tw; for(int k = 0; k < 4; ++k) { th = i + dh[k]; tw = j + dw[k]; if(th < 0 || th >= h || tw < 0 || tw >= w || v[th][tw] == 1 || !isConnect(i, j, th, tw, ((k&1)?HENG:ZONG))) continue; dfs(th, tw); } } int main() { int ans; while(scanf("%d%d", &h, &w)) { if(h < 0 || w < 0) break; ans = 0; for(int i = 0; i < h; ++i) scanf("%s", mp[i]); memset(v, 0, sizeof(v)); for(int i = 0; i < h; ++i) for(int j = 0; j < w; ++j) if(v[i][j] == 0) { ++ans; dfs(i, j); } printf("%d\n", ans); } }
Recent Comments