1024

#include<stdio.h> #include<string.h> #define __I_MAX_W__ 100 //标识每一个点是否能向上或向右前进 //不得不说一些，墙的信息指两个点不通 int i_w,i_h; int i_wall_number; int i_x1,i_x2,i_y1,i_y2; unsigned char map_wall[__I_MAX_W__][__I_MAX_W__][2]; short int map_walk[__I_MAX_W__][__I_MAX_W__]; short int map_walk2[__I_MAX_W__][__I_MAX_W__]; unsigned char s_path[__I_MAX_W__*__I_MAX_W__+1]; int i_path_len; typedef struct SNode{ unsigned char x,y; }SNode; SNode s_queue[__I_MAX_W__*__I_MAX_W__]; int i_queue_start; int i_queue_end; typedef struct SWall{ unsigned char x,y,x2,y2; }SWall; SWall s_wall_list[__I_MAX_W__*__I_MAX_W__]; int i_wall_list_use; void fInit() { memset(map_wall,0,__I_MAX_W__*__I_MAX_W__*2); memset(map_walk,0,__I_MAX_W__*__I_MAX_W__*sizeof(short int)); memset(map_walk2,0,__I_MAX_W__*__I_MAX_W__*sizeof(short int)); i_wall_list_use = 0; } int fWalk(unsigned char i_start_x, unsigned char i_start_y, short int map_walk[][__I_MAX_W__]) { i_queue_start = i_queue_end = 0; // printf("**************\n"); s_queue[i_queue_end++] = {i_start_x,i_start_y}; while(i_queue_start != i_queue_end ) { SNode s_node = s_queue[i_queue_start++]; short int i_path_len_t = map_walk[s_node.x][s_node.y]>0?map_walk[s_node.x][s_node.y]:-map_walk[s_node.x][s_node.y]; // if(i_path_len_t == i_path_len+1) // { // break; // } //四个方向探测 // printf("%d %d %d\n",s_node.x,s_node.y,map_walk[s_node.x][s_node.y]); unsigned char i_next_x,i_next_y; for(int i = 0 ;i < 4 ; ++i) { int i_status = 0; switch(i) { case 0://R if(s_node.x+1<i_w&&map_wall[s_node.x][s_node.y][0]==0) { i_status = 1; i_next_x = s_node.x+1; i_next_y = s_node.y; } break; case 1://L if(s_node.x-1>=0&&map_wall[s_node.x-1][s_node.y][0]==0) { i_status = 1; i_next_x = s_node.x-1; i_next_y = s_node.y; } break; case 2://U if(s_node.y+1<i_h&&map_wall[s_node.x][s_node.y][1]==0) { i_status = 1; i_next_x = s_node.x; i_next_y = s_node.y+1; } break; case 3://D if(s_node.y-1>=0&&map_wall[s_node.x][s_node.y-1][1]==0) { i_status = 1; i_next_x = s_node.x; i_next_y = s_node.y-1; } break; } if(i_status) { if(map_walk[i_next_x][i_next_y] == 0) { s_queue[i_queue_end++] = {i_next_x,i_next_y}; map_walk[i_next_x][i_next_y] =i_path_len_t+1; }else if(map_walk[i_next_x][i_next_y] < 0) { short int i_value = - map_walk[i_next_x][i_next_y]; if(i_value > i_path_len_t +1 ) { return 0; }else if(i_value == i_path_len_t+1) { if(map_walk[s_node.x][s_node.y]>0) { return 0; }else { s_queue[i_queue_end++] = {i_next_x,i_next_y}; } } } } } } // for(int j = 0 ;j < i_h;++j) // { // for(int i = 0;i< i_w;++i) // { // printf("d",map_walk[i][j]>0?map_walk[i][j]:-map_walk[i][j]); // } // printf("\n"); // } // printf("\n"); return 1; } int fCheckWalkMust() { for(int i = 0 ;i < i_wall_list_use;++i) { int i_status = 0; short int i_start_len = map_walk[s_wall_list[i].x][s_wall_list[i].y]; short int i_end_len = map_walk2[s_wall_list[i].x2][s_wall_list[i].y2]; if(i_start_len == 0 || i_end_len == 0) { return 0; } if (i_start_len < 0){i_start_len = - i_start_len;} if(i_end_len < 0){i_end_len = - i_end_len;} if(i_end_len+i_start_len > i_path_len +2 ||i_start_len==0 ||i_end_len ==0) { ++i_status; } i_start_len = map_walk2[s_wall_list[i].x][s_wall_list[i].y]; i_end_len = map_walk[s_wall_list[i].x2][s_wall_list[i].y2]; if(i_start_len == 0 || i_end_len == 0) { return 0; } if (i_start_len < 0){i_start_len = - i_start_len;} if(i_end_len < 0){i_end_len = - i_end_len;} if(i_end_len+i_start_len > i_path_len +2 ||i_start_len==0 ||i_end_len ==0) { ++i_status; } if(i_status == 2) { return 0; } } return 1; } int main() { int t; scanf("%d",&t); while(t-->0) { int i_status = 1; scanf("%d %d",&i_w,&i_h); scanf("%s\n",s_path); scanf("%d",&i_wall_number); fInit(); while(i_wall_number-- >0) { scanf("%d %d %d %d",&i_x1,&i_y1,&i_x2,&i_y2); s_wall_list[i_wall_list_use++] = {i_x1,i_y1,i_x2,i_y2}; if (i_x1 + 1 == i_x2) { map_wall[i_x1][i_y1][0]=1; }else if(i_y1+1 == i_y2) { map_wall[i_x1][i_y1][1]=1; }else if(i_x1 == i_x2+1) { map_wall[i_x2][i_y2][0] = 1; }else { map_wall[i_x2][i_y2][1] = 1; } } i_path_len = strlen((const char*)s_path); int i_x,i_y; i_x = i_y = 0; int i = 2; map_walk2[0][0] = -i_path_len-1; map_walk[0][0] = -1; for(unsigned char* p_path = s_path; *p_path != '\0'; ++p_path,++i) { switch(*p_path) { case 'R': if(map_wall[i_x][i_y][0] == 1) { i_status = 0; } ++i_x; break; case 'L': if(map_wall[i_x-1][i_y][0] == 1) { i_status = 0; } --i_x; break; case 'U': if(map_wall[i_x][i_y][1] == 1) { i_status = 0; } ++i_y; break; case 'D': if(map_wall[i_x][i_y-1][1] == 1) { i_status = 0; } --i_y; break; } map_walk[i_x][i_y] = -i; map_walk2[i_x][i_y] = - (i_path_len + 2 - i); } if(i_status == 0 || fWalk(0,0,map_walk) == 0 || fWalk(i_x,i_y,map_walk2) == 0 || fCheckWalkMust() == 0) { printf("INCORRECT\n"); }else { printf("CORRECT\n"); } } return 0; }