#include<stdio.h>
#include<string.h>
#include<math.h>
#include <list>
#include <map>
#define MAP_SIZE 102
unsigned char map[MAP_SIZE][MAP_SIZE];
unsigned char* p_map = (unsigned char*)map;
int i_map_x,i_map_y;
int i_dot_number;
int i_one_block_chunk;
int i_two_block_chunk;
int i_three_block_chunk_1;
int i_three_block_chunk_2;
unsigned char ca_chunk_info_buf[MAP_SIZE*MAP_SIZE];
int i_chunk_info_buf_user;
typedef struct SChunk{
int i_block_number;
unsigned char* p_chunk_info_start;
unsigned long int i_hash_value;
unsigned char ui8_chunk;
}SChunk;
SChunk sa_chunks[125];
std::map<unsigned long int,std::list<SChunk*>* > map_chunk;
int fCheckChunkSample(SChunk* p_a,SChunk* p_b)
{
if(p_a->i_block_number!=p_b->i_block_number)
{
return 0;
}
unsigned char* p_start = p_a->p_chunk_info_start;
unsigned char* p_end = p_a->p_chunk_info_start+p_a->i_block_number-2;
unsigned char* p_start_b = p_b->p_chunk_info_start;
for(;p_start != p_end&&(*p_start)==(*p_start_b);++p_start,++p_start_b);
return p_start == p_end ? 1: 0;
}
void fMapADDChunk(SChunk* p_data)
{
std::map<unsigned long int, std::list<SChunk* >* >::iterator it = map_chunk.find(p_data->i_hash_value) ;
if(it==map_chunk.end())
{
std::list<SChunk*>* list_data = new std::list<SChunk*>();
list_data->push_back(p_data);
map_chunk[p_data->i_hash_value]=list_data;
}else
{
std::list<SChunk*>* list_data = (std::list<SChunk*>*)it->second;
for(std::list<SChunk*>::iterator it = list_data->begin();it!= list_data->end();++it)
{
SChunk* p_chunk_a = (SChunk*)(*it);
if(fCheckChunkSample(p_chunk_a,p_data) == 1)
{
++p_chunk_a->ui8_chunk;
return;
}
}
list_data->push_back(p_data);
}
}
int fMapDelChunk(SChunk* p_data)
{
std::map<unsigned long int,std::list<SChunk*>* >::iterator it = map_chunk.find(p_data->i_hash_value) ;
if(it==map_chunk.end())
{
return 0;
}else
{
std::list<SChunk*>* list_data = (std::list<SChunk*>*)it->second;
for(std::list<SChunk*>::iterator it2 = list_data->begin();it2!= list_data->end();++it2)
{
SChunk* p_chunk_a = (SChunk*)*it2;
if(fCheckChunkSample(p_chunk_a,p_data) == 1)
{
if(p_chunk_a->ui8_chunk == 1)
{
list_data->remove(p_chunk_a);
if(list_data->empty())
{
delete(list_data);
map_chunk.erase(it);
}
}else
{
--p_chunk_a->ui8_chunk;
}
return 1;
}
}
return 0;
}
}
int i_schunk_number;
unsigned char uca_hash[16] = {0,1,1,2,1,3,2,4,1,3,3,4,2,4,4,5};
unsigned long long int ui32[6] = {0x10100000,0x01,0x0100,0x010000,0x01000000,0x1010};
unsigned char uca_tmp_chunk[MAP_SIZE*MAP_SIZE];
int i_tmp_chunk_len ;
unsigned char tmp_map[100*100];
void fInitMap()
{
memset(map,0,MAP_SIZE*MAP_SIZE);
}
void fInit()
{
fInitMap();
i_one_block_chunk = 0;
i_two_block_chunk = 0;
i_three_block_chunk_1 = 0;
i_three_block_chunk_2 = 0;
i_chunk_info_buf_user = 0;
}
void fInputMapInfo()
{
int i_x,i_y;
for(int i =0;i<i_dot_number;++i)
{
scanf("%d %d",&i_x,&i_y);
map[i_x+1][i_y+1] = 1;
}
}
#define __I_ADD_X__ 1
#define __I_DEL_X__ 2
#define __I_ADD_Y__ 3
#define __I_DEL_Y__ 4
int ia_value[8] = {0x02,0x04,0x08,0x10,0x20,0x40,0x80,0x00};
int ia_value2[8] = {0x01,0x03,0x07,0x0f,0x1f,0x3f,0x7f,0xff};
int ia_value3[4] = {0x01,0x02,0x04,0x08};
typedef struct SNode{
unsigned char x;
unsigned char y;
// void SNode(unsigned char x,unsigned char y)
// {
// this->x = x;
// this->y = y;
// }
}SNode;
SNode sa_stack[100*100];
int i_len = 0;
void fUpdateChunkValue(SChunk* p_chunk,
int i_start_x,
int i_start_y,
int i_time,
int ia_order[]
)
{
int i_value = ia_value[i_time];
int i_value2 = ia_value2[i_time];
unsigned char * p_value_start = p_chunk->p_chunk_info_start;
int i_value_len = 0;
int i_status = 0;
i_len = 0;
sa_stack[i_len++] = {i_start_x,i_start_y};
map[i_start_x][i_start_y] = i_value;
while(i_len !=0)
{
unsigned char uc = 0;
SNode s_now = sa_stack[--i_len];
for(int i = 0; i < 4;++i)
{
switch(ia_order[i])
{
case __I_ADD_X__:
if( ((map[s_now.x+1][s_now.y])&(i_value2)) != 0)
{
sa_stack[i_len++] = {s_now.x+1,s_now.y};
uc |= ia_value3[i];
map[s_now.x+1][s_now.y] = i_value;
}
break;
case __I_DEL_X__:
if( ((map[s_now.x-1][s_now.y])&(i_value2)) != 0)
{
sa_stack[i_len++] = {s_now.x-1,s_now.y};
uc |= ia_value3[i];
map[s_now.x-1][s_now.y] = i_value;
}
break;
case __I_ADD_Y__:
if(((map[s_now.x][s_now.y+1])&(i_value2)) != 0)
{
sa_stack[i_len++] = {s_now.x,s_now.y+1};
uc |= ia_value3[i];
map[s_now.x][s_now.y+1] = i_value;
}
break;
case __I_DEL_Y__:
if(((map[s_now.x][s_now.y-1])&(i_value2)) != 0)
{
sa_stack[i_len++] = {s_now.x,s_now.y-1};
uc |= ia_value3[i];
map[s_now.x][s_now.y-1] = i_value;
}
break;
}
}
if(i_status == 1)
{
*p_value_start = uc;
}else
{
if (*p_value_start > uc)
{
return ;
}else if(*p_value_start < uc )
{
i_status = 1;
*p_value_start = uc;
}
}
++i_value_len;
++p_value_start;
}
p_chunk->i_block_number = i_value_len;
}
unsigned long int fGetHash(unsigned char* p_start,unsigned char* p_end)
{
int b = 378551;
int a = 63689;
long long int hash = 0;
for(; p_start != p_end; ++p_start)
{
hash = hash * a + *p_start;
a = a * b;
}
return (hash & 0x7FFFFFFF);
}
void fFindOneChunk(SChunk* p_chunk,
int i_start_x,
int i_start_y)
{
//不一定增加，所以不要现在就加一
int i_x_s,i_x_m,i_y_s,i_y_m;
i_x_s = i_x_m = i_start_x;
i_y_s = i_y_m = i_start_y;
SNode sa_start_poiter[7];//只需要记录入口的必要信息,比如顶部的左侧或右侧的x坐标
int i_use = 0;
int i_time = 0;
// 4个方向优先级 (i_x_def,0) > (0,i_y_def) > (-i_x_def,0) > (0,-i_y_def)
//遍历一次更新 8 个入口，并记录当次 路径string
//顺序使用剩下的入口，如果变小则直接结束，如果，变大则直接替换，并继续
//知道最后得到最大值路径。并计算hash值
int i_value = ia_value[i_time];
int i_value2 = ia_value2[i_time];
int ia_order[4] = {__I_ADD_X__,__I_DEL_X__,__I_ADD_Y__,__I_DEL_Y__};
i_len = 0;
sa_stack[i_len++] = {i_start_x,i_start_y};
map[i_start_x][i_start_y] = i_value;
while(i_len !=0)
{
unsigned char uc = 0;
SNode s_now = sa_stack[--i_len];
for(int i = 0; i < 4;++i)
{
switch(ia_order[i])
{
case __I_ADD_X__:
if( ((map[s_now.x+1][s_now.y])&(i_value2)) != 0)
{
sa_stack[i_len++] = {s_now.x+1,s_now.y};
uc |= ia_value3[i];
map[s_now.x+1][s_now.y] = i_value;
if(s_now.x+1 > i_x_m)
{
i_x_m = s_now.x+1;
}
}
break;
case __I_DEL_X__:
if( ((map[s_now.x-1][s_now.y])&(i_value2)) != 0)
{
sa_stack[i_len++] = {s_now.x-1,s_now.y};
uc |= ia_value3[i];
map[s_now.x-1][s_now.y] = i_value;
if(s_now.x-1<i_x_s)
{
i_x_s = s_now.x-1;
}
}
break;
case __I_ADD_Y__:
if(((map[s_now.x][s_now.y+1])&(i_value2)) != 0)
{
sa_stack[i_len++] = {s_now.x,s_now.y+1};
uc |= ia_value3[i];
map[s_now.x][s_now.y+1] = i_value;
if(s_now.y+1>i_y_m)
{
i_y_m = s_now.y+1;
}
}
break;
case __I_DEL_Y__:
if(((map[s_now.x][s_now.y-1])&(i_value2)) != 0)
{
sa_stack[i_len++] = {s_now.x,s_now.y-1};
uc |= ia_value3[i];
map[s_now.x][s_now.y-1] = i_value;
if(s_now.y-1<i_y_s)
{
i_y_s = s_now.y-1;
}
}
break;
}
}
p_chunk->p_chunk_info_start[p_chunk->i_block_number] = uc;
++p_chunk->i_block_number;
}
switch(p_chunk->i_block_number)
{
case 1:
++i_one_block_chunk;
return ;
case 2:
++i_two_block_chunk;
return ;
default:
break;
}
//获取其他几个入口
//Top + Right
for(int i = i_x_m;i>=i_x_s;--i)
{
if(map[i][i_y_s] == 2)
{
sa_start_poiter[i_use ++ ] = {i,i_y_s};
break;
}
}
//Bottom + Left
for(int i = i_x_s;i<=i_x_m;++i)
{
if(map[i][i_y_m] == 2)
{
sa_start_poiter[i_use ++ ] = {i,i_y_m};
break;
}
}
//Bottom + Reght
for(int i = i_x_m;i>=i_x_s;--i)
{
if(map[i][i_y_m] == 2)
{
sa_start_poiter[i_use ++ ] = {i,i_y_m};
break;
}
}
//Left + Top
for(int i = i_y_s;i <= i_y_m ; ++i)
{
if (map[i_x_s][i] == 2)
{
sa_start_poiter[i_use++] = {i_x_s,i};
break;
}
}
//Left+Bottom
for(int i = i_y_m;i >= i_y_s ; --i)
{
if (map[i_x_s][i] == 2)
{
sa_start_poiter[i_use++] = {i_x_s,i};
break;
}
}
//Right + Top
for(int i = i_y_s;i <= i_y_m ; ++i)
{
if (map[i_x_m][i] == 2)
{
sa_start_poiter[i_use++] = {i_x_m,i};
break;
}
}
//Right+ Bottom
for(int i = i_y_m;i >= i_y_s ; --i)
{
if (map[i_x_m][i] == 2)
{
sa_start_poiter[i_use++] = {i_x_m,i};
break;
}
}
int iaa_order[7][4] ={{__I_DEL_X__,__I_ADD_X__,__I_ADD_Y__,__I_DEL_Y__},
{__I_ADD_X__,__I_DEL_X__,__I_DEL_Y__,__I_ADD_Y__},
{__I_DEL_X__,__I_ADD_X__,__I_DEL_Y__,__I_ADD_Y__},
{__I_ADD_Y__,__I_DEL_Y__,__I_ADD_X__,__I_DEL_X__},
{__I_DEL_Y__,__I_ADD_Y__,__I_ADD_X__,__I_DEL_X__},
{__I_ADD_Y__,__I_DEL_Y__,__I_DEL_X__,__I_ADD_X__},
{__I_DEL_Y__,__I_ADD_Y__,__I_DEL_X__,__I_ADD_X__}};
for(int i = 0;i < 7 ;++i)
{
fUpdateChunkValue(p_chunk,sa_start_poiter[i].x,sa_start_poiter[i].y,i+1,iaa_order[i]);
}
unsigned char* p_start = p_chunk->p_chunk_info_start;
unsigned char* p_end = p_chunk->p_chunk_info_start+p_chunk->i_block_number;
p_chunk->i_hash_value = fGetHash(p_start,p_end);
}
void fInitChunkTotal()
{
for (int i = 1;i<= i_map_x;++i)
{
for(int j = 1;j<= i_map_y;++j)
{
if(map[i][j] == 1)
{//发现一个块
SChunk* p_chunk = sa_chunks + i_schunk_number;
p_chunk->p_chunk_info_start = ca_chunk_info_buf+i_chunk_info_buf_user;
p_chunk->i_block_number = 0;
p_chunk->i_hash_value = 0;
p_chunk->ui8_chunk = 1;
fFindOneChunk(p_chunk,i,j);
if (p_chunk->i_block_number > 2)
{
i_chunk_info_buf_user += p_chunk->i_block_number - 2;
++i_schunk_number;
fMapADDChunk(p_chunk);
}
}
}
}
}
int fChunkMapChunkTotal()
{
for (int i = 1;i<= i_map_x;++i)
{
for(int j = 1;j<= i_map_y;++j)
{
if(map[i][j] == 1)
{//发现一个块
SChunk* p_chunk = sa_chunks + i_schunk_number;
p_chunk->p_chunk_info_start = ca_chunk_info_buf+i_chunk_info_buf_user;
p_chunk->i_block_number = 0;
p_chunk->i_hash_value = 0;
fFindOneChunk(p_chunk,i,j);
if(p_chunk->i_block_number == 1)
{
if (--i_one_block_chunk < 0)
{
return 0;
}
}else if(p_chunk->i_block_number == 2)
{
if (--i_two_block_chunk < 0)
{
return 0;
}
}else if(fMapDelChunk(p_chunk) == 0)
{
return 0;
}
}
}
}
return 1;
}
void fClearMapChunk()
{
while(map_chunk.empty()== false)
{
delete(map_chunk.begin()->second);//(std::list<SChunk*>*)it->second;
map_chunk.erase(map_chunk.begin());
}
}
int main()
{
int i_test_time;
scanf("%d",&i_test_time);
while(i_test_time-- > 0)
{
fInit();
scanf("%d %d %d",&i_map_x,&i_map_y,&i_dot_number);
fInputMapInfo();
fInitChunkTotal();
fInitMap();
fInputMapInfo();
if (fChunkMapChunkTotal() )
{
printf("YES\n");
}else{
printf("NO\n");
}
fClearMapChunk();
}
}
转载请注明原文地址: https://ju.6miu.com/read-679715.html
