---
author: little
tags: Hành tinh đầm lầy
title: Hành tinh đầm lầy Solution
---

$\Huge\text{Hành tinh đầm lầy Solution}$

-------

:::info
📌 Tags: `bfs`
✍️ Writer: little
📋 Content:
[TOC]
:::

-----

## Thuật toán

Ta có công thức để biết trạng thái của ô $(x, y)$ tại thời điểm $tm$ là $(a_{x,y} - tm$ % $4 + 4)$ % $4$.

Gọi $dist[i][j][cur]$ là khoảng thời gian ngắn nhất để di chuyển robot đi từ ô $(n, 1)$ đến ô $(i, j)$ và trạng thái hiện tại của ô $(i, j)$ là $cur$.

Vì ta phải biết thời điểm hiện tại là bao nhiêu nên ta sẽ lưu trong $queue$ là $pair$ chứa ô hiện tại và thời điểm hiện tại. Thì khi duyệt đến ô $(x, y)$ và ta sẽ tính xem trạng thái của ô kế tiếp là gì để di chuyển sang ô đó.

----

Tham khảo code ở [đây](https://ideone.com/7vZMHC)