2013
12-03

诡异的楼梯

Hogwarts正式开学以后,Harry发现在Hogwarts里,某些楼梯并不是静止不动的，相反,他们每隔一分钟就变动一次方向.

5 5
**..T
**.*.
..|..
.*.*.
S....

7
Hint

Hint





/*

HDU 1180 诡异的楼梯
*/

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
#define CLR(c,v) (memset(c,v,sizeof(c)))

const int M = 25;
const int inf = 1 << 30;
const char t1 = '|';
const char t2 = '-';
const char start = 'S';
const char end = 'T';
const char obstacle = '*';
const char inqueue = '#';

char map[M][M];
int n,m;
int revise[][2] = {{-1,0},
{0,-1},{0,1},
{1,0}};
struct _P{
int x;int y;int minite;
_P(int x = -1, int y = -1): x(x), y(y) {minite = 0;}
bool operator < (const _P &a) const {
return minite > a.minite;
}
bool operator == (const _P &a) const {
return minite == a.minite;
}
}S;

int BFS(){
priority_queue <_P > que;
que.push(S);
while(!que.empty()){
_P now = que.top(); que.pop();
if (end == map[now.x][now.y]){ // 终点
return now.minite;
}
map[now.x][now.y] = obstacle;
for (int i = 0; i < 4 ; i++){ // 四个方向
int next_x = revise[i][0] + now.x;
int next_y = revise[i][1] + now.y;
if (next_x >= 0 && next_x < n && next_y >= 0 && next_y < m ){ // 没有出界
if (map[next_x][next_y] == obstacle){
continue;
}else if (map[next_x][next_y] == road || map[next_x][next_y] == end ){ // 如果是路或终点
_P next = _P(next_x , next_y);
next.minite = now.minite + 1;
(map[next_x][next_y] != end)?(map[next_x][next_y] = inqueue):(1);
que.push(next);
}else if ((map[next_x][next_y] == t1 || map[next_x][next_y] == t2 )&&  // 如果是梯子
((map[revise[i][0]*2 + now.x][revise[i][1]*2 + now.y] != obstacle)  )){ // 并且梯子的另一边是路
if (0 == i || 3 == i){ // 上下方向的梯子
if (revise[i][0]*2 + now.x >= 0 && revise[i][0]*2 + now.x < n  ){// 没有出界
if ((map[next_x][next_y] == t1 && (now.minite & 1) == 0) ||
(map[next_x][next_y] == t2 && (now.minite & 1) == 1) ){
// 梯子恰好能过去
_P next = _P( revise[i][0]*2 + now.x , now.y);
next.minite = now.minite + 1;
//map[next_x][next_y] = obstacle;
que.push(next);
}else{  // 如果暂时不能过去
_P next = _P( now.x , now.y);
next.minite = now.minite + 1;
que.push(next);
}
}
}else if (1 == i || 2 == i ){ // 左右方向的梯子
if (revise[i][1]*2 + now.y >= 0 && revise[i][1]*2 + now.y < m){// 没有出界
if ((map[next_x][next_y] == t1 && (now.minite & 1) == 1) ||
(map[next_x][next_y] == t2 && (now.minite & 1) == 0) ){
// 梯子恰好能过去
_P next = _P( now.x , revise[i][1]*2 + now.y);
next.minite += now.minite + 1;
//map[next_x][next_y] = obstacle;
que.push(next);
}else{	// 如果暂时不能过去
_P next = _P( now.x ,  now.y);
next.minite += now.minite + 1;
que.push(next);
}
}
}
}
}
}
}
return 0;
}

int main(){
//freopen("Input.txt","r",stdin);
//freopen("out.txt","w",stdout);
while(scanf("%d %d",&n , &m) != EOF ){
for (int i = 0; i < n ; i ++){
scanf("%s",map[i]);
for (int j = 0 ; j < m ; j++){
if (start == map[i][j]){
S = _P(i,j);
}
}
}
printf("%d\n", BFS() );
}
return 0;
}

/*

20 20
-.|...-............S
.-.|...-............
|.-.|...-...........
.|.-.|...-..........
..|.-.|...-.........
-..|.-.|...-........
.-..|.-.|...-.......
..-..|.-.|...-......
...-..|.-.|...-.....
....-..|.-.|...-....
.....-..|.-.|...-...
......-..|.-.|...-..
.......-..|.-.|...-.
........-..|.-.|...-
.........-..|.-.|...
..........-..|.-.|..
...........-..|.-.|.
............-..|.-.|
.............-..|.-.
T.............-..|.-
2 4
...T
S-..
3 4
.|S-
.*|.
T.*.
1 10
S-.|.-.-.T
1 1
T
20 1
S
-
.
-
.
-
.
-
.
-
.
-
.
-
.
-
.
-
.
T
1 2
ST
2 1
T
S
20 20
...................S
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
T...................
20 20
...................T
....................
|*******************
....................
*******************-
....................
|*******************
....................
*******************-
....................
|*******************
....................
*******************|
....................
-*******************
....................
*******************|
....................
-*******************
S...................
5 5
**..T
**.*.
**|..
**.**
S..**
5 5
.*..T
...*.
.-.*.
..|**
S-.**
5 5
.|.-T
-*-*|
.*.|.
-*-**
S|.**
5 5
S....
-|-|-
.....
-|-|-
....T
1 3
S-T
1 3
S|T
1 5
S|.|T
1 5
S-.-T
1 5
S|.-T
1 5
S-.|T
2 2
*T
S|
20 20
**.|.**.-.*|..-.*..T
.*|..-.*..**.-.|*..*
....|..|.|.-..-..|..
.-.**..*...-..-..*..
**.-.**..*-.-..*.*.|
.-...|.|...**..-.*..
.*|.-.-*.|.-.*-*.**.
-..*.*.*-.**.|.|*.*|
.-.*-..-...-..-..|..
-.-..*.**.|.*|.*..*-
.*|..-.*..**.-.|*..*
....|..|.|.-..-..|..
**.-.**..*-.-..*.*.|
.-.*-..-...-..-..|..
.-...|.|...**..-.*..
.*|.-.-*.|.-.*-*.**.
-..*.*.*-.**.|.|*.*|
.-.*-..-...-..-..|..
-.-..*.**.|.*|.*..*-
S|.*.*.|.-*.|.*.|.-.
10 20
**.|.**.-.*|..-.*..T
.*|..-.*..**.-.|*..*
....|..|.|.-..-..|..
**.-.**..*-.-..*.*.|
.-...|.|...**..-.*..
.*|.-.-*.|.-.*-*.**.
-..*.*.*-.**.|.|*.*|
.-.*-..-...-..-..|..
-.-..*.**.|.*|.*..*-
S|.*.*.|.-*.|.*.|.-.
4 9
-..-.-.|T
.*-*..*..
.*.*.***|
S-..*..*.
6 10
.|.*.|.*.T
****.-...*
***..-|*.*
-.**.***..
.-.|.*-*..
S.***-*.**

*/

1. 问题3是不是应该为1/4 .因为截取的三段，无论是否能组成三角形， x， y-x ，1-y,都应大于0，所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.

2. Gucci New Fall Arrivals

This is really nice to know. I hope it will be successful in the future. Good job on this and keep up the good work.

3. #!/usr/bin/env python
def cou(n):
arr =
i = 1
while(i<n):
arr.append(arr[i-1]+selfcount(i))
i+=1
return arr[n-1]

def selfcount(n):
count = 0
while(n):
if n%10 == 1:
count += 1
n /= 10
return count