[20180310 PRO] Map Completion

#include "stdafx.h"

#define MAX_MAP_SIZE 64
#define ZONE_SIZE 4

char zone[ZONE_SIZE][ZONE_SIZE];
int hisindex=0;
char hiszone[100000][ZONE_SIZE][ZONE_SIZE];

extern void randomscan(char zone[ZONE_SIZE][ZONE_SIZE]);

int calc_and_upmap(int N,char guess[64][64],char zone[4][4])
{
   int i,j,x,y;
   int inner=0;
   int stx,sty;
   int meetnum;
   int upnum=0;//初始化为0
   for(stx=0;stx<=N-4;stx+=2){
      for(sty=0;sty<=N-4;sty+=2){
         meetnum=0;
         for(i=0;i<ZONE_SIZE;i++){
            for(j=0;j<ZONE_SIZE;j++){
               if(guess[stx+i][sty+j]==zone[i][j])
                  meetnum++;
            }
         }
         if(meetnum>=8){
            for(i=0;i<4;i++)
               for(j=0;j<4;j++)
                  guess[stx+i][sty+j]=zone[i][j];
            inner=1;
            upnum=16-meetnum;
            break;//找到一个匹配就要中断
         }
      }
      if(inner==1){
         break;
      }
   }
   return upnum;
}

//保存random,这里可以优化为不重复的zone
void save_zone_info(char zone[4][4])
{
   int i,j;
   for(i=0;i<4;i++){
      for(j=0;j<4;j++){
         hiszone[hisindex][i][j]=zone[i][j];
      }
   }
   hisindex+=1;
}

int update_by_hiszone(int N, char guess[64][64])
{
   int i,j;
   int index;
   int upnum=0;
   char hzone[4][4];
   for(index=0;index<hisindex;index++){
      for(i=0;i<ZONE_SIZE;i++){
         for(j=0;j<ZONE_SIZE;j++){
            hzone[i][j]=hiszone[index][i][j];
         }
      }
      upnum=calc_and_upmap(N,guess,hzone);
      if(upnum>0)//首先要记得这里如果upnum大于0，说明已经找到匹配，这里开始写成8，导致死循环。
         break; //因为题目保证了只能匹配一块区域，所以这里要中断
   }
   return upnum;
}

void reconstruct(int N, char guess[MAX_MAP_SIZE][MAX_MAP_SIZE])//map=guess_map
{
   int upnum;
   int leftnum=(N-4)*(N-4);
   char zone[4][4];
   while(leftnum != 0){
      randomscan(zone);
      upnum=calc_and_upmap(N,guess,zone);
      if(upnum!=0)//有更新
      {
         leftnum-=upnum;//更新剩余的方格
         leftnum-=update_by_hiszone(N,guess);//用历史zone更新
      }
      save_zone_info(zone);
   }
   hisindex=0;//每个case结束后要复位
}

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif

#include <stdio.h>

#define MAX_MAP_SIZE        64
#define ZONE_SIZE            4

#define MAX_SCAN_COUNT        100000

extern void reconstruct(int N, char map[MAX_MAP_SIZE][MAX_MAP_SIZE]);

static char map[MAX_MAP_SIZE][MAX_MAP_SIZE];
static int N;
static int seed;
static int scancount;

static int pseudo_rand() {
    seed = seed * 214013 + 2531011;
    return (seed >> 16) & 0x7fff;
}

void randomscan(char zone[ZONE_SIZE][ZONE_SIZE]) {
    if (scancount >= MAX_SCAN_COUNT)
        return;

    int x0 = (pseudo_rand() % ((N - ZONE_SIZE) / 2 + 1)) * 2; // x0 = 0, 2, 4, ..., N - 4
    int y0 = (pseudo_rand() % ((N - ZONE_SIZE) / 2 + 1)) * 2; // y0 = 0, 2, 4, ..., N - 4

    for (int y = 0; y < ZONE_SIZE; ++y)
    for (int x = 0; x < ZONE_SIZE; ++x)
        zone[y][x] = map[y + y0][x + x0];

    ++scancount;
}

static void makemap() {
    for (int y = 0; y < N; ++y)
    for (int x = 0; x < N; ++x)
        map[y][x] = pseudo_rand() % 15 + 1;
}

static bool compare(char map1[MAX_MAP_SIZE][MAX_MAP_SIZE], char map2[MAX_MAP_SIZE][MAX_MAP_SIZE]) {
    for (int y = 0; y < N; ++y)
    for (int x = 0; x < N; ++x)
        if (map1[y][x] != map2[y][x])
            return false;

    return true;
}

int main() {
    int TC, totalscore, totalscan;

    //freopen("sample_input.txt", "r", stdin);

    setbuf(stdout, NULL);
    scanf("%d", &TC);

    totalscore = totalscan = 0;
    for (int testcase = 1; testcase <= TC; ++testcase) {
        char guess[MAX_MAP_SIZE][MAX_MAP_SIZE];
        int min_scan_count;

        scanf("%d %d %d", &N, &seed, &min_scan_count);

        makemap();

        scancount = 0;

        for (int y = 0; y < N; ++y)
        for (int x = 0; x < N; ++x)
            guess[y][x] = 0;

        for (int k = 0; k < N; ++k) {
            guess[k][0] = map[k][0];
            guess[0][k] = map[0][k];
            guess[k][1] = map[k][1];
            guess[1][k] = map[1][k];
            guess[k][N - 1] = map[k][N - 1];
            guess[N - 1][k] = map[N - 1][k];
            guess[k][N - 2] = map[k][N - 2];
            guess[N - 2][k] = map[N - 2][k];
        }

        reconstruct(N, guess);

        if (!compare(map, guess))
            scancount = MAX_SCAN_COUNT;
        totalscan += scancount;

        int score;
        if (TC == 5) { // sample testcase
            score = scancount < MAX_SCAN_COUNT ? 100 : 0;
            totalscore += score;
        } else { // eval testcase
            score = scancount <= min_scan_count + (min_scan_count / 2) ? 100 : 0;
            totalscore += score;
        }

        printf("#%d %d\n", testcase, score);
    }

    if (totalscan > MAX_SCAN_COUNT) totalscan = MAX_SCAN_COUNT;
    printf("total score = %d, total scan = %d\n", totalscore / TC, totalscan);
    return 0;
}
/*
5
8 26585 3
12 24059 28
16 26751 50
20 19164 100
24 10446 153
*/