POJ1059 Chutes and Ladders

题目大意：

　　有一种叫做“Chutes and Ladders”（梯子和滑梯）的简单游戏。游戏在一块棋盘上进行，棋盘上有编号从1-100的格子，玩家们从假定的编号为0的格子处出发。各玩家轮流投掷色子（上有数字1-6），色子的数字表示玩家在棋盘上将前进的步数，最先到达100号格子的玩家胜利。

　　当然游戏不会仅仅这么无聊。在棋盘上不同的格子之间可能通过Ladder(梯子，从编号小的格子连至编号大的格子)和“Chute”(滑梯，从编号大的格子连至编号小的格子)连接起来。如果，一次投色子后前进到达的格子处是ladder或chute的起点，则玩家将到达ladder或chute通向的格子。注意：终点格子处的ladder和chute都是无效的，但起点处的有效。

　　此外，有一些特殊的格子：写有“miss-a-turn”的格子表示玩家一旦到达它们，将失去下一轮的投色子前进机会，写有“extra-turn”的格子表示玩家可以立即再投一次色子再前进一次。起点和终点处的格子都不会是这两种特殊格子。

　　如果一个玩家当前处于编号95以上的格子处，如果它们投掷的色子使它们前进的终点超过了100，那么这次这次投掷将被忽略。

输入：输入的开始为少于1000次的色子投掷结果，每个都是1到6的整数，由6表示结束。

　　接下来是一个或多个游戏数据集。每个数据集包含三个部分。

　　第一部分：一行表示游戏中的玩家数，多于1少于6。

　　第二部分：棋盘中的ladders和chutes. ladders和chutes每个都由两个1-99的整数表示起点和终点。当遇到一行“0 0”时表示该部分结束。

　　第三部分：棋盘中的“miss-a-turn”格和“extra-turn”格。每行一个，如果数字是负数说明是“miss-a-turn”, 正数说明是“extra-turn”（例如：-15表示15号格是"miss-a-turn"格, 25表示25号格是“extra-turn”）.0表示该部分结束。

输出：每轮游戏对应1行，输出该轮游戏的赢家编号，输入已保证会找到赢家。

Sample Input

3 6 3 2 5 1 3 4 2 3 1 2 0
2
6 95
99 1
0 0
-3
98
0
2
3 99
6 90
0 0
0
0

Sample Output

2
2

模拟题水过。

  1 ////////////////////////////////////////////////////////////////
  2 //        POJ1059 Chutes and Ladders
  3 //        Memory: 228K        Time: 0MS
  4 //        Language: C++        Result : Accepted
  5 ///////////////////////////////////////////////////////////////
  6 
  7 #include <iostream>
  8 #include <algorithm>
  9 
 10 using namespace std;
 11 
 12 struct Ladder {
 13     int start;
 14     int end;
 15 };
 16 
 17 int die[1000];
 18 int counter[6];
 19 bool trapped[6];
 20 int player_num;
 21 Ladder ladders[200];
 22 int ladder_cnt;
 23 bool miss_turn[101];
 24 bool extra_turn[101];
 25 
 26 int cmp(Ladder &a, Ladder &b) {
 27     return a.start <= b.start;
 28 }
 29 
 30 int bin_seach(int v, int s, int e) {
 31     if (s > v || v > ladders[e].start || v < ladders[s].start) {
 32         return -1;
 33     }
 34     int mid = (s + e) / 2;
 35     if (v == ladders[mid].start) {
 36         return ladders[mid].end;
 37     } else if (v < ladders[mid].start) {
 38         return bin_seach(v, s, mid - 1);
 39     } else {
 40         return bin_seach(v, mid + 1, e);
 41     }
 42 }
 43 
 44 int main(void) {
 45     
 46     //读入色子投掷结果
 47     for (int i = 0; i < 1000; ++i) {
 48         cin >> die[i];
 49         if (die[i] == 0) {
 50             break;
 51         }
 52     }
 53 
 54     while (cin >> player_num && player_num > 0) {
 55         
 56         //读取玩家数
 57         memset(miss_turn, false, sizeof(miss_turn));
 58         memset(extra_turn, false, sizeof(extra_turn));
 59         memset(counter, 0, sizeof(counter));
 60         memset(ladders, 0, sizeof(ladders));
 61         ladder_cnt = 0;
 62 
 63         //读取ladders
 64         while (true) {
 65             cin >> ladders[ladder_cnt].start >> ladders[ladder_cnt].end;
 66             if (ladders[ladder_cnt].start == 0) {
 67                 break;
 68             }
 69             ++ladder_cnt;
 70         }
 71 
 72         //ladders排序
 73         sort(ladders, ladders + ladder_cnt, cmp);
 74 
 75         //读入miss-a-turn和extra-turn
 76         while (true) {
 77             int t;
 78             cin >> t;
 79             if (t > 0) {
 80                 extra_turn[t] = true;
 81             } else if (t < 0) {
 82                 miss_turn[-1 * t] = true;
 83             } else {
 84                 break;
 85             }
 86         }
 87 
 88         //Game starts!
 89         int player_id = 0;
 90         int die_pointer = 0;
 91         while (true) {
 92 
 93             int current = counter[player_id];    //当前位置
 94             int die_num = die[die_pointer++];    //色子投掷结果
 95             int des = current + die_num;        //目标位置
 96 
 97             if (current == 100) {
 98                 cout << player_id + 1 << endl;
 99                 break;
100             }
101 
102             //当前玩家被困
103             if (trapped[player_id]) {
104                 trapped[player_id++] = false;
105                 player_id %= player_num;
106                 continue;
107             }
108 
109             //恰好到达终点，结束
110             if (des == 100) {
111                 cout << player_id + 1 << endl;
112                 break;
113             }
114             //超过100，忽略该次
115             else if (des > 100) {
116                 (++player_id) %= player_num;
117                 continue;
118             }
119 
120             counter[player_id] = des;
121             
122             //判断该处是否有ladder或chute
123             des = bin_seach(counter[player_id], 0, ladder_cnt - 1);
124             if (des != -1) {
125                 counter[player_id] = des;
126             }
127 
128             //判断该处是否为miss-a-turn或extra-turn
129             if (miss_turn[counter[player_id]] == true) {
130                 trapped[player_id] = true;
131             }
132             if (extra_turn[counter[player_id]] == true) {
133                 continue;
134             }
135             (++player_id) %= player_num;
136         }
137     }
138     return 0;
139 }

View Code