Home > ACM > HDU Farm Irrigation 1198

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);
    }
}
Categories: ACM Tags: , ,
  1. No comments yet.
  1. No trackbacks yet.