Ý tưởng:

Thực hiện theo trình tự dãy thao tác đã cho các quy tắc nêu trong đề bài:

• Nếu đầu con rắn vượt ra ngoài màn hình, trò chơi kết thúc.
• Nếu đầu con rắn đi vào ô có quả táo, chiều dài con rắn tăng lên.
• Nếu mình con rắn cùng ô với đầu con rắn (con rắn tự cắn), trò chơi kết thúc.

Tổ chức dữ liệu:

• A[][]: Trạng thái ban đầu của màn hình, A[i][j]=1 nếu ô (i,j) có quả táo.
• B[][], với B[i][j] = t: con rắn bò đến ô (i,j) ở thời điểm t.
• L: độ dài của con rắn.
• D: Thời gian của trò chơi.

Thuật toán:

• (r,s): Vị trí ô đầu con rắn đang bò đến (thay đổi theo hướng rẽ): r = r + dr[i]; s = s + ds[i]; int dr[] = { 0, 1, 0, -1 }; int ds[] = { 1, 0, -1, 0 };

  Nếu c == ‘L’ thì i= (i+3)%4; Nếu c==’D’ thì i=(i+1)%4;

• Trường hợp con rắn bò ra ngoài: ( r < 0 || s < 0 || r >= N || s >= N ).

• Trường hợp con rắn đi vào ô có quả táo: L++, A[r][s] =0;
• Trường hợp con rắn tự cắn: D - B[r][s] <= L;

Code:

include <bits/stdc++.h>

define MAX_N 100

define MAX_TIME 10000

int dr[] = { 0, 1, 0, -1 }; int ds[] = { 1, 0, -1, 0 };

int A[MAXN][MAXN]; int B[MAXN][MAXN];

void xuat( int ans ) { printf( "%d\n", ans - 1 ); exit( 0 ); }

int main( void ) { int N, K, L, i, r, s; int D, h, LL;

scanf( "%d%d", &N, &K );

for( r = 0; r < N; ++r ) for( s = 0; s < N; ++s ) B[r][s] = -1;

for( i = 0; i < K; ++i ) { scanf( "%d%d", &r, &s ); A[--r][--s] = 1; }

D = 1; LL = 1; h = 0;

scanf( "%d", &L );

B[r = 0][s = 0] = 0; for( i = 0; i <= L; ++i ) { int Dturn = MAX_TIME + 1; char c = 'L';

if( i < L ) scanf( "%d %c", &Dturn, &c );

while( D <= Dturn ) { D++;

  r += dr[h];
  s += ds[h];

  // Vuot gioi han
  if( r < 0 || s < 0 || r >= N || s >= N )
    xuat( D );

 //An qua tao
  if( A[r][s] )
  {
    A[r][s] = 0;
    LL++;
  }

  // Tu can minh
  if( D - B[r][s] <= LL )
    xuat( D );

  // Thoi diem qua o (r,s)
  B[r][s] = D;
}

// c
if( c == 'L' )
  h = (h + 3) % 4;
else // if( c == 'D' )
  h = (h + 1) % 4;

}

return 0; }