Background

:::info[Problem Background]

“Did we really return to the correct timeline?”

Fieren’s voice was very soft, yet it seemed to make the once quiet air in the woods pause for a moment.

What came into view was still the familiar forest from when they arrived. Tall trees stood silently in the morning mist; scattered, slightly chilly light leaked through the branches and leaves; the damp smell of soil and the fresh scent of plants drifted slowly. Even the gray-white rock not far away, split by a thin crack, looked almost exactly the same as when they first stepped into this place. Everything felt too natural, too calm, as if the earlier experiences of traveling through time, changing the timeline, and then putting everything back had never really happened.

But precisely because of that, it was even harder to feel at ease.

After all, nobody knows what the cost of traveling through time truly is. This overly familiar scenery—had they really returned to the original world, or was it a gentle illusion woven by ancient magic? Even Fieren herself could not easily tell.

Shutalk looked around for a while, and his expression, rarely, did not relax.

“It just feels… too smooth,” he said in a low voice.

“Yeah.” Frieren looked up at the sky cut into pieces by the leaves, still calm. “Let’s go back to Rozema Mining Town and take a look first. If it’s still the same as before, then the timeline has probably returned to normal.”

This was the safest plan for now.

So the three of them set off again in the direction they remembered, trying to pass through the forest and return to the road they had taken. However, before long, Fieren gradually frowned. Those seemingly ordinary tree shadows, forked paths, moss-covered stones, and bushes appeared to be repeating little by little. After walking further, Shutalk finally stopped, staring at the dead log lying beside the tree roots ahead, and his expression became somewhat stiff.

“This… haven’t we seen it just now?”

Fieren was silent for a moment, then nodded lightly.

Only then did they realize something—since everything around the “Sinking Star Library” had returned to its original state along with time, the ancient disorientation spell in this forest had naturally been restored as well.

“Damn.” Shutalk sighed. “We’ve started walking in circles again.”

The mist in the woods still quietly wound between the trees. The wind passed through the treetops, making faint, repetitive rustling sounds. If they had not just experienced that journey across time, this scenery should have looked peaceful and ordinary; but at this moment, it was like a silently closing net, gently yet stubbornly trapping the three of them in place once again.

Fieren softly let out a breath, as if she finally remembered something, and turned to Frieren.

“By the way, when we came, didn’t you draw a map of this forest?”

“Mm.” Frieren nodded, then reached out and opened the notebook she carried with her.

The pages flipped lightly between her fingertips, and finally stopped at an old map with complicated routes drawn on it. It did record intersections in the forest and several obvious landmarks, but compared with the route map they later truly walked and gradually completed earlier, this page was clearly much more rough. Many key routes were still blank, and some intersections were only guesses that had not been verified yet.

Frieren looked down for a moment and said calmly:

“—Ah, as expected.”

“What’s wrong?” Fieren asked.

“It seems time has been restored to even earlier than I thought.” Frieren slightly closed the notebook, then opened it again to take another look. “This map is still incomplete.”

题目描述

Problem Description

The old route map that was drawn in the past now only remains as an $n\times m$ grid. Each cell is:

• .: verified passable empty ground.
• #: unverified suspected trap.

Frieren’s group is at the top-left corner $(1, 1)$, and needs to reach Rozema Mining Town at the bottom-right corner $(n, m)$. Each step can only move right or down to an adjacent cell, and they cannot step onto an unverified suspected trap.

Define the number of turns as: during movement, the number of times the path changes from moving right to moving down, or from moving down to moving right. At the start, Frieren may choose any direction to move, so no matter which direction is chosen for the very first step, the number of turns is $0$. Also, after turning you must move; you cannot turn in place without moving. That is not a valid turn.

Frieren’s group wants to reach Rozema Mining Town quickly, so at most one turn is allowed. However, they also do not want the trip to be too boring, so they must turn at least once. Please determine whether there exists a valid path whose number of turns is exactly $1$.

Input Format

The first line contains two integers $n, m(1\leq n\times m\leq 10^5)$, representing the size of the forest grid.

The next $n$ lines each contain a string of length $m$, describing the layout of the forest. It is guaranteed that each character in the string is either . or #.

Output Format

Output YES or NO, indicating whether there exists a valid path whose number of turns is exactly $1$.

3 4
....
.##.
....

YES

3 3
...
.##
#..

NO

Hint

In Sample 1, you can choose to go down from $(1, 1)$ to $(3, 1)$ first, then after turning go right to $(3, 4)$; or go right to $(1, 4)$ first, then after turning go down to $(3, 4)$. Both plans can reach the target with only $1$ turn.

In Sample 2, it is not hard to prove that there is no turning plan that can reach the target.

:::info[Problem Background]

After walking for who knows how much longer, that dull feeling of looping around in the woods finally began to loosen bit by bit.

The first thing to arrive was an extremely faint, yet incredibly familiar, sound of metal being struck. It drifted intermittently from far away through layers of tree shadows and the evening wind, as if someone were standing by a furnace in the deepening dusk, hammering ore that had not yet cooled, one strike after another. Right after that, a few very thin strands of white smoke appeared at the end of the treetops, rising quietly into the sky dyed orange-gold by the setting sun, as silent as a dream that had finally returned to the human world.

Fieren froze for a moment, and her steps unconsciously slowed by half a beat. She stared toward that distant place held between the trees and the evening glow; her eyes gradually lit up, and even the last trace of unease weighing on her heart seemed to slowly disperse along with that wisp of smoke.

“It’s right ahead!” she said, almost unable to hold it back, her voice finally carrying a long-lost lightness.

Shutalk also looked in the direction of her gaze, and his previously tense expression finally eased. Frieren said nothing, only quietly raised her head and looked toward the exit filled with warm daylight. The evening wind brushed past the tall canopy; leaves rubbed against one another, making fine and gentle rustling sounds, as if giving a final farewell to this long journey.

The further they went, the clearer the smell in the air became. The damp scent of plants gradually faded, replaced by the warmth of furnaces, smoke, and an evening meal that was almost ready. The gaps between the trees also became wider little by little, and the road once covered by shadows was finally dyed with the color of dusk again. The sun was slowly sinking behind the mountains, coloring the whole forest a gentle and quiet golden red, and stretching the three of them’s shadows very, very long, slanting across the path covered with fallen leaves and碎石 (suì shí).

And within that flowing evening glow, the forest exit was already close at hand.

Input Format

The first line contains two integers $n, m(1\leq n\times m\leq 10^5)$, representing the size of the forest grid.

The next $n$ lines each contain a string of length $m$, describing the layout of the forest. It is guaranteed that each character in the string is either . or #.

Output Format

Output YES or NO, indicating whether there exists a valid path whose number of turns is exactly $1$.

Hint

In Sample 1, you can choose to go down from $(1, 1)$ to $(3, 1)$ first, then after turning go right to $(3, 4)$; or go right to $(1, 4)$ first, then after turning go down to $(3, 4)$. Both plans can reach the target with only $1$ turn.

In Sample 2, it is not hard to prove that there is no turning plan that can reach the target.

Translated by ChatGPT 5