Hang băng

Đề bài

Mô tả

Bạn đang ở một tầng của hang băng nhiều tầng. Để đi tiếp, bạn phải rơi xuống tầng dưới, và cách duy nhất là rơi xuyên qua lớp băng.

Tầng hang hiện tại là một lưới chữ nhật gồm n hàng và m cột. Mỗi ô chứa băng nguyên vẹn hoặc băng đã nứt. Từ ô đang đứng, bạn chỉ có thể bước sang một ô kề cạnh (không được đứng yên tại chỗ). Khi bạn bước sang một ô:

  • Nếu ô đó là băng đã nứt, bạn rơi xuyên qua ô đó xuống tầng dưới.
  • Nếu ô đó là băng nguyên vẹn, lớp băng ở ô đó bị nứt và bạn đứng lại trên ô đó.

Các hàng được đánh số từ 1 đến n từ trên xuống dưới, các cột được đánh số từ 1 đến m từ trái sang phải. Ký hiệu (r,c) là ô ở hàng r, cột c.

Bạn đang đứng ở ô (r1,c1), và ô này đã nứt vì bạn vừa rơi từ tầng trên xuống đây. Lối ra xuống tầng kế tiếp nằm ở ô (r2,c2), nên bạn cần rơi xuyên qua đúng ô (r2,c2). Ô lối ra có thể trùng với ô bạn đang đứng.

Hãy xác định xem bạn có thực hiện được điều đó hay không.

Dữ liệu vào

  • Dòng đầu chứa hai số nguyên nm.
  • n dòng tiếp theo mô tả trạng thái ban đầu của tầng hang, mỗi dòng gồm m ký tự "." (băng nguyên vẹn) hoặc "X" (băng đã nứt).
  • Dòng tiếp theo chứa hai số nguyên r1c1 là vị trí ban đầu của bạn. Dữ liệu đảm bảo ô (r1,c1) là ký tự "X".
  • Dòng cuối chứa hai số nguyên r2c2 là toạ độ ô mà bạn cần rơi xuyên qua.

Dữ liệu ra

In ra YES nếu bạn tới được đích, ngược lại in ra NO.

Ràng buộc

  • 1n,m500
  • 1r1,r2n
  • 1c1,c2m

Ví dụ

Input Output Giải thích
4 6
X...XX
...XX.
.X..X.
......
1 6
2 2
YES Ô đích (2,2) ban đầu là băng nguyên vẹn. Bạn đi tới đó một lần làm băng nứt ra, rời đi rồi quay lại; lần bước vào thứ hai bạn rơi xuyên qua đúng ô cần tới.
5 4
.X..
...X
X.X.
....
.XX.
5 3
1 1
NO Không có cách nào rơi xuyên qua ô (1,1).
4 7
..X.XX.
.XX..X.
X...X..
X......
2 2
1 6
YES Ô đích (1,6) vốn đã nứt sẵn, nên chỉ cần đi tới một ô kề nó rồi bước sang là rơi xuống ngay.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.400 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.2 gforth 0.7.3 gfortran 12.2.0 go 1.27.0 groovyc 5.1.1 javac 25.0.4 node 26.8.1 julia 1.12.7 kotlinc 2.4.10 lean 4.33.1 sbcl 2.2.9 lua 5.4.9 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.10 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.14.7 racket 8.7 ruby 4.0.6 rustc 1.98.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.3.3 tclsh 8.6 bun 1.4.0 deno 2.9.6 v 0.5.2 zig 0.16.0