Routing NAT – How Does the Router Know How to Route Packets to My Terminal?

This depends on the NAT implementation.

In general, most NAT engines prefer to make as few modifications as necessary. So, the first one there gets to keep their src port. The second one is "the loser" and has it changed. The map entry doesn't depend on anything changing; it tracks whatever is used, changed or not. As long as they aren't both talking to the same server, they can both use the same src port, because the map includes the destination:

[(inside){src}PC A:123 {dst}Server A:123 :: (outside){src}ISP:123 {dst}Server A:123]
[(inside){src}PC B:123 {dst}Server B:123 :: (outside){src}ISP:123 {dst}Server B:123]
                                                     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

The outside details are different, thus a unique key to find the inside match.

First, just because your two computers are connected via the Internet at two separate locations doesn't necessarily mean that you are using private addresses. That is certainly the most likely scenarios with IPv4, given the IPv4 address shortage, but it is still not necessarily true. If you are running IPv6, you are probably using public IPv6 addresses.

Let's assume you are using private IPv4 addressing behind a router using NAT.

Knowing the other private address does nothing for you at all, so just take that out of the equation.

Under normal, non-hacker circumstances, the NAT routers at each end would need to have port forwarding enabled for each PC's private address, or the routers would need to be using one-to-one NAT, to enable the two PCs to communicate via the public addresses. You could also use a VPN between the two PCs to get around the NAT problem. This all assumes that there are no firewalls in place to block traffic from the Internet into the private networks.

In one-to-one NAT, each network would have multiple public addresses which uniquely translate to a single private address, so using a public address will get you to the corresponding private address. This is also an unlikely scenario given the shortage of IPv4 addresses, but it is done in some places.

Port forwarding configures NAT to forward incoming traffic sent to a router's public address on a given port number to be sent to a particular inside private address at a given port number.

A VPN is a tunnel. Usually, traffic from one inside network is encapsulated within packets addressed to the public address of the other network and sent to the other network where it is de-encapsulated to the other inside network. This can be configured in such a way as to make the foreign network appear local to the tunnel interface of the local network.

A firewall on either end, or anywhere along the path, may be configured to block any or all of these methods.