Backpacking during March

Greetings!

I'll be traveling to Japan in early March 2010 for and leaving in early April 2010. This will be during Cherry Blossom season and I wanted to ask from locals (or at least folks who might know) what the travel accommodations will be like during then.

As I see it, I have two options:

1. Book all my hotel/hostel stays in advance. This ensures I'll have a place to stay and don't end up paying too much for a last minute room. For this option, I'll most likely just optimize my stays so as to save as much money on transportation as possible. The down side to this option is that I can't freely move from place to place and I might miss the Cherry Blossoms if my schedule isn't timed right with when they'll bloom.

2. (my preferred option) I buy the 21-day JR Rail pass and move from region to region as I see fit. I like this option best because it gives me the most freedom and I'm almost guaranteed to be able to travel to a city where the Cherry Blossoms are blooming.. but then again, it is a high tourist season, so hotels/hostels might be fully booked and finding somewhere to stay on short notice might be problematic/expensive.

So to those of you who are in the known: what do you think? During March/early Apil, will I be able to easily find (cheap) places to stay all throughout Japan (like I could if during say the winter months) or will things be booked and overly expensive?

Thanks in advance!

Kyoto is the only city where I strongly recommend to book ahead, especially for Satuday nights.

Tourist resorts also can get very busy on Saturday nights, but are usually no problem on weekdays.

The risk of not finding vacancies obviously increases if you are not flexible with respect to budget.

If you travel flexibly, make sure to bring good sources of low-budget accommodations, such as Lonley Planet and Hostelworld.