O(1) 的小乐

/*
ID: lvxiaol3
LANG: C++
TASK: ttwo
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

char grid[10][10];

/* delta x, delta y position for moving north, east, south, west */
int deltax[] = { 0, 1, 0, -1 };
int deltay[] = { -1, 0, 1, 0 };

void move(int *x, int *y, int *dir)
{
    int nx, ny;

    nx = *x+deltax[*dir];
    ny = *y+deltay[*dir];

    if(nx < 0 || nx >= 10 || ny < 0 || ny >= 10 || grid[ny][nx] == '*')
        *dir = (*dir + 1) % 4;
    else
    {
        *x = nx;
        *y = ny;
    }
}

int main(void)
{
    FILE *fin, *fout;
    char buf[100];
    int i, x, y;
    int cowx, cowy, johnx, johny, cowdir, johndir;

    fin = fopen("ttwo.in", "r");
    fout = fopen("ttwo.out", "w");
    assert(fin != NULL && fout != NULL);

    cowx = cowy = johnx = johny = -1;

    for(y=0; y<10; y++)
    {
        fgets(buf, sizeof buf, fin);
        for(x=0; x<10; x++)
        {
            grid[y][x] = buf[x];
            if(buf[x] == 'C')
            {
                cowx = x;
                cowy = y;
                grid[y][x] = '.';
            }
            if(buf[x] == 'F')
            {
                johnx = x;
                johny = y;
                grid[y][x] = '.';
            }
        }
    }

    assert(cowx >= 0 && cowy >= 0 && johnx >= 0 && johny >= 0);

    cowdir = johndir = 0; /* north */

    for(i=0; i<160000 && (cowx != johnx || cowy != johny); i++)
    {
        move(&cowx, &cowy, &cowdir);
        move(&johnx, &johny, &johndir);
    }

    if(cowx == johnx && cowy == johny)
        fprintf(fout, "%d\n", i);
    else
        fprintf(fout, "0\n");
    return 0;
}

这个问题的状态的复杂度的确是160000就OK的，但是如果这个问题把规模扩大至 100*100 的图中，就需要一个比较好的算法来做。现在的想法是对于cow求出每个状态的循环节和初始，这个的复杂度才是O(4*10^4) ，然后对于每个点求 cow和john的扩展欧几里得数，并保存最小值，复杂度是O(nlogn) n是4*10^4的复杂度

如果改到这个规模就算是一个比较好的题目了，很显然纯粹模拟就吃不消了