题目分析
本题描述了一种特殊的城市布局：街道（Street\texttt{Street}Street）和大道（Avenue\texttt{Avenue}Avenue）分别呈东西向和南北向，构成网格状结构。每条道路上的门牌号按照特定规律排列：
- 大道编号从西向东递增，街道编号从北向南递增
- 每个街区（
block）两侧各有505050个driveway，一侧编号为00,02,…,9800, 02, \dots, 9800,02,…,98，另一侧为01,03,…,9901, 03, \dots, 9901,03,…,99 - 当沿门牌号增加方向行驶时，奇数号在右侧
- 部分路段可能缺失（不连续），形成死胡同
题目要求：给定若干对地址（表示driveway的位置），计算两点间的最短合法路径长度，距离定义为经过的driveway数量（不包括起点和终点）。
合法驾驶规则：
- 靠右行驶
- 只能在交叉口穿越车道
- 进入或离开
driveway时必须右转 - 除非在死胡同尽头，否则禁止U\texttt{U}U形转弯
解题思路
1. 地址编码与状态表示
每个地址由三部分唯一标识：道路类型（A或S）、道路编号（000000到494949）、门牌号（000000000000到489948994899）。可以使用一个整数进行编码：
id=(code−A)×1000000+index×10000+numberid = (code - \texttt{A}) \times 1000000 + index \times 10000 + numberid=(code−A)×1000000+index×10000+number
2. 缺失路段处理
输入中每个缺失路段给出道路标识和一段连续的门牌号范围（包含边界）。需要注意：缺失的是整个section边界上的道路段，因此如果161216121612不可通行，那么161316131613也不可通行。处理时将范围内的所有门牌号对应的driveway标记为不可用。
3. 图模型抽象
将每个driveway视为图中的一个节点。从一个节点移动到相邻节点的规则取决于：
- 当前所在道路的类型（
A或S） - 当前门牌号的奇偶性（决定行驶方向）
- 当前是否处于道路端点（门牌号为000000、999999等）
4.BFS\texttt{BFS}BFS搜索
由于边权均为111，使用BFS\texttt{BFS}BFS可以求出最短路径。从起点开始，每一步根据当前位置和方向生成后继节点，跳过被标记为缺失的节点。
5. 关键移动规则
以大道（Avenue\texttt{Avenue}Avenue）为例：
北向行驶（门牌号为偶数，即左侧
driveway）：- 普通情况：向前移动到同一条大道的下一个
driveway（门牌号−2-2−2） - 若该位置缺失，则只能进入当前街区对应的街道（右转）
- 在端点（门牌号000000）时，可考虑右转、直行、左转三种选择
- 普通情况：向前移动到同一条大道的下一个
南向行驶（门牌号为奇数，即右侧
driveway）：- 对称处理，门牌号+2+2+2向前移动
街道（Street\texttt{Street}Street）的移动规则类似，只是方向换为东西向。
6.U\texttt{U}U形转弯处理
只有在死胡同末端（所有三个方向都缺失）时才允许U\texttt{U}U形转弯，即掉头沿原路返回。
代码实现
// City Navigation// UVa ID: 176// Verdict: Accepted// Submission Date: 2016-02-26// UVa Run Time: 0.338s#include<bits/stdc++.h>usingnamespacestd;// 存储一个 driveway 的结构体structhouse{charcode;// 'A' 或 'S'intindex;// 道路编号 00~49intnumber;// 门牌号 0000~4899intstep;// BFS 步数};set<int>missing;// 缺失的 driveway 集合set<int>discovered;// BFS 已访问集合house from,to;// 起点和终点// 将 driveway 编码为唯一整数intgetHouseId(house h){return(h.code-'A')*1000000+h.index*10000+h.number;}// 判断 driveway 是否缺失boolisMissing(house h){returnmissing.count(getHouseId(h))>0;}// 判断是否已访问boolisVisited(house h){returndiscovered.count(getHouseId(h))>0;}// 创建 driveway 对象housemakeHouse(charcode,intindex,intnumber,intstep){return(house){code,index,number,step};}// BFS 搜索最短路径voidbfs(){queue<house>next;next.push(from);discovered.clear();discovered.insert(getHouseId(from));while(next.empty()==false){house v=next.front();next.pop();// 到达终点，输出步数（减去起点和终点）if(v.number==to.number&&v.index==to.index&&v.code==to.code){cout<<(v.step-2)<<"\n";break;}// 当前在大道上（南北向）if(v.code=='A'){intsNumber=v.number/100;// 对应的街道编号inthouseNumber=v.number%100;// 门牌号后两位// 北向行驶（偶数门牌号，位于左侧）if(houseNumber%2==0){if(houseNumber==0){// 到达北端点boolnextFound=false;vector<house>temp;// 右转进入街道（东向）if(v.index>0)temp.push_back(makeHouse('S',sNumber,(v.index-1)*100+98,v.step+1));// 直行继续向北（上一条街道）if(sNumber>0)temp.push_back(makeHouse('A',v.index,(sNumber-1)*100+98,v.step+1));// 左转进入街道（西向）if(v.index<49)temp.push_back(makeHouse('S',sNumber,v.index*100+1,v.step+1));for(inti=0;i<temp.size();i++){if(isMissing(temp[i])==false){if(isVisited(temp[i])==false){discovered.insert(getHouseId(temp[i]));next.push(temp[i]);}nextFound=true;}}// 所有方向都缺失 -> U 形转弯if(nextFound==false){house tempHouse=makeHouse('A',v.index,v.number+1,v.step+1);if(isVisited(tempHouse)==false){discovered.insert(getHouseId(tempHouse));next.push(tempHouse);}}}else{// 非端点情况house temp=makeHouse('A',v.index,v.number-2,v.step+1);if(isMissing(temp))// 前方缺失，只能右转进入街道temp=makeHouse('A',v.index,v.number+1,v.step+1);if(isVisited(temp)==false){discovered.insert(getHouseId(temp));next.push(temp);}}}// 南向行驶（奇数门牌号，位于右侧）对称处理if(houseNumber%2==1){if(houseNumber==99){// 到达南端点boolnextFound=false;vector<house>temp;// 右转进入街道（西向）if(v.index<49)temp.push_back(makeHouse('S',sNumber+1,v.index*100+1,v.step+1));// 直行继续向南（下一条街道）if(sNumber<48)temp.push_back(makeHouse('A',v.index,(sNumber+1)*100+1,v.step+1));// 左转进入街道（东向）if(v.index>0)temp.push_back(makeHouse('S',sNumber+1,(v.index-1)*100+98,v.step+1));for(inti=0;i<temp.size();i++){if(isMissing(temp[i])==false){if(isVisited(temp[i])==false){discovered.insert(getHouseId(temp[i]));next.push(temp[i]);}nextFound=true;}}// U 形转弯if(nextFound==false){house tempHouse=makeHouse('A',v.index,v.number-1,v.step+1);if(isVisited(tempHouse)==false){discovered.insert(getHouseId(tempHouse));next.push(tempHouse);}}}else{house temp=makeHouse('A',v.index,v.number+2,v.step+1);if(isMissing(temp))temp=makeHouse('A',v.index,v.number-1,v.step+1);if(isVisited(temp)==false){discovered.insert(getHouseId(temp));next.push(temp);}}}}// 当前在街道上（东西向）处理逻辑类似if(v.code=='S'){intaNumber=v.number/100;// 对应的大道编号inthouseNumber=v.number%100;// 东向行驶（偶数门牌号）if(houseNumber%2==0){if(houseNumber==0){// 东端点boolnextFound=false;vector<house>temp;// 右转进入大道（南向）if(v.index<49)temp.push_back(makeHouse('A',aNumber,v.index*100+1,v.step+1));// 直行继续向东（上一条大道）if(aNumber>0)temp.push_back(makeHouse('S',v.index,(aNumber-1)*100+98,v.step+1));// 左转进入大道（北向）if(v.index>0)temp.push_back(makeHouse('A',aNumber,(v.index-1)*100+98,v.step+1));for(inti=0;i<temp.size();i++){if(isMissing(temp[i])==false){if(isVisited(temp[i])==false){discovered.insert(getHouseId(temp[i]));next.push(temp[i]);}nextFound=true;}}// U 形转弯if(nextFound==false){house tempHouse=makeHouse('S',v.index,v.number+1,v.step+1);if(isVisited(tempHouse)==false){discovered.insert(getHouseId(tempHouse));next.push(tempHouse);}}}else{house temp=makeHouse('S',v.index,v.number-2,v.step+1);if(isMissing(temp))temp=makeHouse('S',v.index,v.number+1,v.step+1);if(isVisited(temp)==false){discovered.insert(getHouseId(temp));next.push(temp);}}}// 西向行驶（奇数门牌号）if(houseNumber%2==1){if(houseNumber==99){// 西端点boolnextFound=false;vector<house>temp;// 右转进入大道（北向）if(v.index>0)temp.push_back(makeHouse('A',aNumber+1,(v.index-1)*100+98,v.step+1));// 直行继续向西（下一条大道）if(aNumber<48)temp.push_back(makeHouse('S',v.index,(aNumber+1)*100+1,v.step+1));// 左转进入大道（南向）if(v.index<49)temp.push_back(makeHouse('A',aNumber+1,v.index*100+1,v.step+1));for(inti=0;i<temp.size();i++){if(isMissing(temp[i])==false){if(isVisited(temp[i])==false){discovered.insert(getHouseId(temp[i]));next.push(temp[i]);}nextFound=true;}}// U 形转弯if(nextFound==false){house tempHouse=makeHouse('S',v.index,v.number-1,v.step+1);if(isVisited(tempHouse)==false){discovered.insert(getHouseId(tempHouse));next.push(tempHouse);}}}else{house temp=makeHouse('S',v.index,v.number+2,v.step+1);if(isMissing(temp))temp=makeHouse('S',v.index,v.number-1,v.step+1);if(isVisited(temp)==false){discovered.insert(getHouseId(temp));next.push(temp);}}}}}}intmain(intargc,char*argv[]){cin.tie(0);cout.sync_with_stdio(false);string line;intstart,end;// 读取缺失路段部分，直到 '#'while(cin>>line,line!="#"){cin>>start>>end;// 标记该路段上连续的门牌号为缺失for(inti=start;i<=end+1;i++){house temp=(house){line.front(),stoi(line.substr(1)),i,0};missing.insert(getHouseId(temp));}}// 读取地址对部分，直到 '#'while(cin>>line,line!="#"){cin>>start;from=(house){line.front(),stoi(line.substr(1)),start,1};cin>>line>>end;to=(house){line.front(),stoi(line.substr(1)),end,0};bfs();// 对每一对地址进行 BFS 搜索}return0;}总结
本题的核心在于将城市道路网络转化为图模型，并模拟靠右行驶的交通规则。BFS\texttt{BFS}BFS保证找到最短路径，关键在于正确处理各种移动情况：直行、左转、右转以及死胡同中的U\texttt{U}U形转弯。理解门牌号与行驶方向的关系是解决问题的前提。
