/*
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;
}
這個(gè)問題的狀態(tài)的復(fù)雜度的確是160000就OK的，但是如果這個(gè)問題把規(guī)模擴(kuò)大至 100*100 的圖中，就需要一個(gè)比較好的算法來做。現(xiàn)在的想法是對(duì)于cow求出每個(gè)狀態(tài)的循環(huán)節(jié)和初始，這個(gè)的復(fù)雜度才是O(4*10^4) ，然后對(duì)于每個(gè)點(diǎn)求 cow和john的擴(kuò)展歐幾里得數(shù)，并保存最小值，復(fù)雜度是O(nlogn) n是4*10^4的復(fù)雜度
如果改到這個(gè)規(guī)模就算是一個(gè)比較好的題目了，很顯然純粹模擬就吃不消了