hdu 5386 Cover(暴力求解+想法题)

发布时间:2017-09-05 11:26:35
hdu 5386 Cover(暴力求解+想法题)

有两种操作:
操作L x y,把当前x,这一列全部置为y
操作H x y,把当前,这一行全部置为y。
现在给你n∗n的初始矩阵,以及n∗n的目标矩阵
现在给你m种操作(由以上两种操作构成),问怎么排序这m种操作,才能使得,初始矩阵,经由排序后的操作,构成目标矩阵。
输出排序方案。

解析:

逆向思维,
枚举每个操作,然后判断该操作是不是最后一个操作。(就像撕胶布一样,一条一条的剥离)
判断是否是最后一个操作方法就是:
除去已经用过的点,如果一排都等于当前操作的颜色,那就是最后一个操作。然后再把操作过的点给标记,重复m次。
最后逆向输出记录下的id。

my code

#include #include #include using namespace std; const int INF = 0x3f3f3f3f; const int M = 505; const int N = 105; int tar[N][N]; struct Oper { int x, color, id; Oper() {} Oper(int x, int color, int id) : x(x), color(color), id(id) {} } H[M], L[M]; int nh, nl, n, m; int order[M]; bool visH[M], visL[M]; int check(int x, int color, char type) { if(type == 'H') { for(int i = 1; i <= n; i++) { if(tar[x][i] == INF) continue; if(tar[x][i] != color) return false; } }else { for(int i = 1; i <= n; i++) { if(tar[i][x] == INF) continue; if(tar[i][x] != color) return false; } } return true; } void setColor(int x, char type) { if(type == 'H') { for(int i = 1; i <= n; i++) tar[x][i] = INF; }else { for(int i = 1; i <= n; i++) tar[i][x] = INF; } } void solve() { int cnt = 0; while(cnt < m) { for(int i = 0; i < nh; i++) { if(visH[i]) continue; if(check(H[i].x, H[i].color, 'H')) { setColor(H[i].x, 'H'); visH[i] = true; order[cnt++] = H[i].id; } } for(int i = 0; i < nl; i++) { if(visL[i]) continue; if(check(L[i].x, L[i].color, 'L')) { setColor(L[i].x, 'L'); visL[i] = true; order[cnt++] = L[i].id; } } } } int main() { int T; scanf(%d, &T); while(T--) { scanf(%d%d, &n, &m); int tmp; for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) scanf(%d, &tmp); for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) scanf(%d, &tar[i][j]); memset(visH, false, sizeof(visH)); memset(visL, false, sizeof(visL)); nh = nl = 0; char oper[5]; int x, color; for(int i = 1; i <= m; i++) { scanf(%s%d%d, oper, &x, &color); if(oper[0] == 'H') H[nh++] = Oper(x, color, i); else L[nl++] = Oper(x, color, i); } solve(); printf(%d, order[m-1]); for(int i = m-2; i >= 0; i--) printf( %d, order[i]); puts(); } return 0; }

企业建站2800元起,携手武汉肥猫科技,做一个有见地的颜值派!更多优惠请戳:襄阳网站建设 http://xiangyang.45qun.com