What food is each prefecture known for?

I'm planning to do some traveling around Japan and I'm a HUGE foodie and love to cook and eat all kinds of foods, especially Japanese food. If I'm going from Tokyo to Nagoya and out west to the major cities, can anyone recommend some good foods to try in each prefecture?

Food greatly depends on the season, but personally, I always love to visit a fisherman wharf and ask for a specialty. There is always something I've never tasted before.

https://www.japan-guide.com/e/e620.html

The link that Uco provided pretty much sums it up. Probably could add a few things like puffer fish in Yamaguchi, shirasu in Kanagawa, green tea in Shizuoka...

Another thing to look into is that each region has it's own interpretation of certain dishes. For instance, okonomiyaki. Depending on the region, different ingredients are used. Hiroshima style has different types of noodles as options. Also, the okonomiyaki could be prepared differently. Most regions will layer all the ingredients, but in Osaka, the ingredients are mixed together in a bowl and then put on the the teppan. Another example is unagi. In the Kanto (Tokyo and surrounding prefectures) region, the unagi is filleted from the back and steamed. In the Kansai ( Osaka, Kyoto, Nara, etc) reigion, the unagi is filleted from the belly and grilled. And of course, there are the different styles of ramen from each region. Might be fun to try and compare the different styles.

Sushi is the best food for traveling, sushi originated from the process of preserving fish in fermented rice.

There are a lot of famous foods in each prefecture, since many cities and towns have their own specialties.

My favorite Nagoya specialty is the Kareenikomi Udon (a curry version of Misonikomi Udon). I recommend this restaurant: ι͎s (shachi Ichi) in Osu:
http://www.syachi-ichi.com/

Although it's not technically a "local specialty", Nagoya also has a world-famous pizza restaurant (they won the World Pizza championship competition): Solo Pizza Napoletana

Oyaki is a speciality of Nagano prefecture and there are a lot of places in Nagano station selling it. I went to Irohado (https://www.irohado.com/ ) to try some. They're particularly well known and have been in business since 1918. If you have dietary restrictions, I believe all the Oyaki sold at least at the Nagano station branch are vegan or at least there was a sign saying that when we went in February.

They have limited edition seasonal flavors. My daughter and I both like the kabocha/pumpkin which is a Winter speciality, a lot.

Hokkaido - ramen
Aomori - grilled scallops with miso
Iwate - wanko soba
Miyagi - beef tongue

To add to what others have said...

In Nagoya, miso katsu is definitely something to try and the local chicken, Nagoya cochin, is also excellent.
Tochigi is famous for strawberries.
Gifu has Hida Beef.
Hiroshima has okonomiyaki.
Nagasaki has champon noodles.
Kagawa has sanuki udon.
Kagoshima has black pork and sweet potato.
Niigata has noppe stew
Ishikawa is known for crab
Mie is known for lobster and Ise udon noodles.