继续是misof 数字教学里面的习题~ 第一篇的最后一道题了~
Problem Statement
You are in a maze containing revolving doors. The doors can be turned 90 degrees by pushing against them in either direction. You are to find a route from the start square to the end square that involves revolving as few doors as possible. Given a map of the maze, determine the fewest number of door revolutions necessary to get from the start to the end.
In the map:
' ': empty space
'#': wall
'O': center of a revolving door (letter "oh", not zero)
'-': horizontal door (always adjacent to a 'O')
'|': vertical door (always adjacent to a 'O')
'S': start square
'E': end square
Each revolving door will always be oriented horizontally (with two horizontal segments) or vertically (with two vertical segments):
|
O or -O-
|
Doors can be revolved 90 degrees by moving onto a door segment from any of the 4 squares diagonally adjacent to the door center, i.e., the 'X' characters below:
X|X X X
O or -O-
X|X X X
Here is an example map:
###
#E#
## #
#### ##
# S -O-#
# ### #
# #
########
In this example, 2 door revolutions are necessary to get from 'S' to 'E'. The first turn is shown here:
### ###
#E# #E#
## # ## #
#### ## #### |##
# S -O-# # S OX#
# ### X# # ###| #
# # # #
######## ########
And the second turn is shown here:
### ###
#E# #E#
## # ## #
####X|## #### X##
# S O # # S -O-#
# ###| # # ### #
# # # #
######## ########
Your method should return an int, the minimum number of door revolutions necessary to get from the start square to the end square. If there is no way to reach the end square, return -1.
Definition
Class:
RevolvingDoors
Method:
turns
Parameters:
vector <string>
Returns:
int
Method signature:
int turns(vector <string> map)
(be sure your method is public)
Notes
-
Assume that all squares off the edge of the map are walls.
Constraints
-
map will contain between 3 and 50 elements, inclusive.
-
Each element of map will contain between 3 and 50 characters, inclusive.
-
Each element of map will contain the same number of characters.
-
Each character in map will be one of 'S', 'E', 'O', '-', '|', '#', and ' ' (space).
-
There will be exactly one 'S' and one 'E' in map.
-
There will be between 1 and 10 doors, inclusive, and they will be formatted in map as described in the problem statement.
-
No two doors will be close enough for any part of them to occupy the same square.
-
It is not allowed for a door to be blocked and unable to turn. There will not be any walls in any of the 4 squares immediately adjacent to the center of a door, nor will a door be on the edge of the map.
关键是门的状态表示，参考了网站上的代码，挑了一个比较简练的，用的优先级队列。写完调好发现TLE 囧~ copy出网站上的再run依然TLE``` ``` 看了下发现现在的system testing 比原来增加了几个测试用例~~~ 于是找出misof大牛的解法，发现对状态处理一样的~~~只不过用了memo和deque，省去了优先级队列调整的时间开销，改好了就pass了~ 上代码~~：
Code Snippet
using namespace std;
typedef long long int64;
typedef vector<int> VI;
typedef vector<string> VS;
#define inf 1000000
#define REP(i,n) for(int (i)=(0);((i)<(n));++(i))
template<class T> inline void checkmin(T &a,const T &b) { if (b<a) a=b; }
template<class T> inline void checkmax(T &a,const T &b) { if (b>a) a=b; }
int dr[]={-1,0,1,0};
int dc[]={0,1,0,-1};
struct state{state(int x,int y,int z,int s):r(x),c(y),doorstate(z),best(s){}int r;int c;int doorstate;int best;};
int memo[56][56][1<<11];
class RevolvingDoors
{
public:
int turns(vector <string> mp)
{
int x=mp.size()+2;int y=mp[0].size()+2;
int sr,sc,er,ec,cnt=0,doorInit=0;
REP(i,x-2)mp[i]='#'+mp[i]+'#'; //trick:modify the pattern to make it easy to loop
mp.insert(mp.begin(),string(58,'#'));
mp.push_back(string(58,'#'));
REP(i,x)REP(j,y)if(mp[i][j]=='S'){mp[i][j]=' ';sr=i;sc=j;}else if(mp[i][j]=='E'){mp[i][j]=' ';er=i;ec=j;}
REP(i,x)REP(j,y)if(mp[i][j]=='O'){if(mp[i-1][j]=='|')doorInit|=(1<<cnt);
mp[i-1][j]=mp[i+1][j] = 100 + cnt*2 +1; //use the content in the box to identify the door number,and the door pos
mp[i][j-1]=mp[i][j+1] = 100 + cnt*2 ; //if pos==0 it means this box is on the left or right of the door
cnt++; mp[i][j]='#';
}
REP(i,x)REP(j,y)REP(t,1<<cnt) memo[i][j][t] = inf; //init the memo
deque<state> Q; Q.push_back(state(sr,sc,doorInit,0));
while(!Q.empty()){
state now=Q.front();Q.pop_front();
int r=now.r , c=now.c , door=now.doorstate , b=now.best;
if( memo[r][c][door] < b)continue; //no better ,no vist
REP(dir,4){ //try four direction
int nr=r+dr[dir],nc=c+dc[dir];
if(mp[nr][nc]==' '){
if(memo[nr][nc][door] > b){ memo[nr][nc][door]=b;Q.push_back(state(nr,nc,door,b));}
}
else if(mp[nr][nc]=='#')continue;
else{ //if we come to a box near to the door-mid
int doornum=(mp[nr][nc]-100)/2;int open=(mp[nr][nc]-100)%2;
if( ((door>>doornum)&1) != open){ //lucily,the box is empty
if(memo[nr][nc][door] > b){memo[nr][nc][door] = b;Q.push_back(state(nr,nc,door,b));}
}
else { // the box has a door
if(open==0 && dr[dir]==0) continue; //try to define the relative pos between the direction and the box
if(open==1 && dc[dir]==0) continue; //also ~ if we cannot push the door we give up
int ndoor=door^(1<<doornum); //we can go into the box if we push the door ~
if(memo[nr][nc][ndoor] > b+1 ){memo[nr][nc][ndoor] = b+1 ;Q.push_back(state(nr,nc,ndoor,b+1));}
}
}
}
}
int ans=inf;
REP(i,1<<cnt){ //loop to check the best ans~
if(memo[er][ec][i]<ans){ans=memo[er][ec][i];cout<<er<<" "<<ec<<" "<<hex<<i<<endl;}
}
if(ans == inf) return -1;
else return ans;
}
中文copy是乱码···囧啊~~ 俺的破烂英文注释啊~~~