首页 > ACM题库 > HDU-杭电 > hdu 3955 March待解决[解题报告]C++
2015
04-14

hdu 3955 March待解决[解题报告]C++

March

问题描述 :

During a game of Civilization V, much of your time will be spent moving units around the world. You’ll be marching your army units off to discover stuff or to fight with your neighbors.
Level up

The world is comprised of hexagons. Generally, units move from hexagon to hexagon, paying the "Movement Cost" required to enter the new hexagon.
Movement Points:
All army units have a certain number of "Movement Points"(MPs) that they can expend on movement in every turn. Once they’ve expended those MPs, they can’t move any more until the next turn.
Expending MPs:
Units expend MPs to enter tiles. The terrain of the tile determines the MP cost of the move. It doesn’t cost anything to leave your current tile; the MP cost is determined by the tile you’re entering.
A unit can always move one tile if it has any MPs left.It doesn’t matter how expensive the tile is; as long as the unit has some MPs left, it can enter.
Terrain of the tile:
Open terrain like Grassland and Plains cost 1 MP to enter, while Forest and Jungle costs 2.
Zones of Control:
Enemy units exert a "Zone of Control"(ZOC) over the tiles around them. When a unit moves between two tiles within enemys’ ZOC it expends all of MPs.(you can’t move on the tile which contain an enemy)
Road:
As long as the unit moves from one tile containing a road into another tile containing a road,the unit will expend just 0.25 MPs no matter what terrain of the tile.(unless within an enemy’s ZOC)
Rivers:
Rivers are between two tiles.
As long as the unit moves cross a rivers from a tile to another tile it expends all of MPs(unless these tiles contain roads).

Giving the information of the World, please tell me the minimum turns to cost for reaching the destination.

输入:

The first line is a number T(1<=T<=30), represents the number of case. The next T blocks follow each indicates a case.
The first line of each case contains three integers N, M(2<=N,M<=100), indicating the size of World, and MP(1<=MP<=10).
Then N lines follow, each line contains M integers.
Each module number tells the information of the tile and is the sum of up to ten integers:
1: Grassland and Plains
2: Forest and Jungle
4: Road
8: Enemy
16: A river on northeast of the tile
32: A river on east of the tile
64: A river on southeast of the tile
128: A river on southwest of the tile
256: A river on west of the tile
512: A river on northwest of the tile
(each tile must contain either 1 or 2)
Then a line with two coordinates x1,y1,x2,y2(0<=x1,x2<n,0<=y1,y2<m) indicating the source and destination. There is no enemy in source and destination and source is different from destination.
The picture below shows the coordinate of the World.
Level up

输出:

The first line is a number T(1<=T<=30), represents the number of case. The next T blocks follow each indicates a case.
The first line of each case contains three integers N, M(2<=N,M<=100), indicating the size of World, and MP(1<=MP<=10).
Then N lines follow, each line contains M integers.
Each module number tells the information of the tile and is the sum of up to ten integers:
1: Grassland and Plains
2: Forest and Jungle
4: Road
8: Enemy
16: A river on northeast of the tile
32: A river on east of the tile
64: A river on southeast of the tile
128: A river on southwest of the tile
256: A river on west of the tile
512: A river on northwest of the tile
(each tile must contain either 1 or 2)
Then a line with two coordinates x1,y1,x2,y2(0<=x1,x2<n,0<=y1,y2<m) indicating the source and destination. There is no enemy in source and destination and source is different from destination.
The picture below shows the coordinate of the World.
Level up

样例输入:

3
2 2 10
97 257
513 1
0 0 1 1

2 2 1
101 262
513 2
0 0 1 1

3 3 2
5 5 5
10 10 5
1 1 5
0 0 2 2

样例输出:

Case 1: 2
Case 2: 1
Case 3: 4
Hint
Case 1: (0,0)->(0,1)->(1,1) First turn cross a river, you expends all of MPs. So you need waiting second turn to reach (1,1) Case 2: (0,0)->(0,1)->(1,1) There are roads on these tiles, so you cross the river expends 0.25 MPs, then expends the remain MPs to reach (1,1). Case 3: (0,0)->(0,1)->(0,2)->(1,2)->(2,2) Even if there are roads on these tiles, but there are all in ZOC, so you will expends all of MPs each move.


  1. 博主您好,这是一个内容十分优秀的博客,而且界面也非常漂亮。但是为什么博客的响应速度这么慢,虽然博客的主机在国外,但是我开启VPN还是经常响应很久,再者打开某些页面经常会出现数据库连接出错的提示

  2. 博主您好,这是一个内容十分优秀的博客,而且界面也非常漂亮。但是为什么博客的响应速度这么慢,虽然博客的主机在国外,但是我开启VPN还是经常响应很久,再者打开某些页面经常会出现数据库连接出错的提示

  3. 漂亮。佩服。
    P.S. unsigned 应该去掉。换行符是n 不是/n
    还可以稍微优化一下,
    int main() {
    int m,n,ai,aj,bi,bj,ak,bk;
    while (scanf("%d%d",&m,&n)!=EOF) {
    ai = sqrt(m-1);
    bi = sqrt(n-1);
    aj = (m-ai*ai-1)>>1;
    bj = (n-bi*bi-1)>>1;
    ak = ((ai+1)*(ai+1)-m)>>1;
    bk = ((bi+1)*(bi+1)-n)>>1;
    printf("%dn",abs(ai-bi)+abs(aj-bj)+abs(ak-bk));
    }
    }