HDU 连连看 1175
题目地址
注意该题不能从外面绕
判断两点是否可以消去
消去可能是可以直接一条横线连,也可能是一个折的线或者是二个折的线
我用的方法,可以同时全部考虑进去
假设A,B是两个要判断是否消去的点,如果两点数字不同,或者都为0,当然不能消去
否则计算出A,B两点向四个方向能延伸到多远
以
1 2 3 4
0 0 0 0
4 3 2 1
为例
如果A=(1,1),B=(3,4)(坐标从1开始)
那么A按上右下左的顺序能延伸的范围是1, 1, 2, 1
B按上右下左的顺序能延伸的范围是2, 4, 3, 4
即向上下的话,是记录其纵坐标的范围,左右的话是记录横坐标的范围
现在先来判断上下是否连接,
那么先得出A,B两者左右延伸的公共范围,易知A左右延伸为(1,1),B为(4,4)故其没有公共范围
再来判断左右是否连接
那么先得出A,B两者上下延伸的公共范围,易知A上下延伸为(1,2),B为(2,3)故其公共范围为(2,2)
遍历纵坐标为(2,2)中的所有数且横坐标为A的横坐标的点,看每个点左右延伸范围是否有包括B点,如果有则可以消去
注意到两点刚好邻接的情况,应该将延伸范围左右扩大1
例如
1 1
这个明显可以消去,但如果按延伸范围是否包括的话,则为不能消去,所以必须加1,注意到代码注释的地方
#include <iostream> using namespace std; int a[1001][1001], h, w; const int dh[] = {-1, 0, 1, 0}; const int dw[] = {0, 1, 0, -1}; struct Point { int h, w; int dir[4]; } st, en; void cal(Point v, int *p) { Point tmp; for(int i = 0; i < 4; ++i) { tmp = v; do { tmp.h += dh[i]; tmp.w += dw[i]; } while(tmp.h >= 0 && tmp.h < h && tmp.w >= 0 && tmp.w < w && a[tmp.h][tmp.w] == 0); tmp.h -= dh[i]; tmp.w -= dw[i]; p[i] = ((i&1) ? tmp.w : tmp.h); } } void cal1(Point v, int *p, int i) { Point tmp; tmp = v; do { tmp.h += dh[i]; tmp.w += dw[i]; } while(tmp.h >= 0 && tmp.h < h && tmp.w >= 0 && tmp.w < w && a[tmp.h][tmp.w] == 0); tmp.h -= dh[i]; tmp.w -= dw[i]; p[i] = ((i&1) ? tmp.w : tmp.h); } bool solve() { if(a[st.h][st.w] == 0 || a[st.h][st.w] != a[en.h][en.w]) return false; int mmin, mmax; cal(st, st.dir); cal(en, en.dir); Point a1 = st, a2 = en; if(a1.w > a2.w) swap(a1, a2); mmin = max(a1.dir[0], a2.dir[0]); mmax = min(a1.dir[2], a2.dir[2]); Point tmp; tmp.w = a1.w; for(int i = mmin; i <= mmax; ++i) { tmp.h = i; cal1(tmp, tmp.dir, 1); //这里必须加1,理由看开头注释 if(tmp.dir[1] + 1 >= a2.w) return true; } if(a1.h > a2.h) swap(a1, a2); mmin = max(a1.dir[3], a2.dir[3]); mmax = min(a1.dir[1], a2.dir[1]); tmp.h = a1.h; for(int i = mmin; i <= mmax; ++i) { tmp.w = i; cal1(tmp, tmp.dir, 2); //这里必须加1,理由看开头注释 if(tmp.dir[2] + 1 >= a2.h) return true; } return false; } int main() { int p; while(scanf("%d%d", &h, &w)) { if(h == 0 && w == 0) break; for(int i = 0; i < h; ++i) for(int j = 0; j < w; ++j) scanf("%d", &a[i][j]); scanf("%d", &p); while(p--) { scanf("%d%d%d%d", &st.h, &st.w, &en.h, &en.w); st.h -= 1, st.w -= 1, en.h -= 1, en.w -= 1; solve() ? puts("YES") : puts("NO"); } } return 0; }
Recent Comments