首页 > 代码库 > The 2014 ACMICPC Asia Regional Guangzhou Online
The 2014 ACMICPC Asia Regional Guangzhou Online
这场网赛当时自己完成了的也就是两道地图题，过去好久了才想到还是该记录下来...
【C】
Wang Xifeng‘s Little Plot
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
【Problem Description】
《Dream of the Red Chamber》(also 《The Story of the Stone》) is one of the Four Great Classical Novels of Chinese literature, and it is commonly regarded as the best one. This novel was created in Qing Dynasty, by Cao Xueqin. But the last 40 chapters of the original version is missing, and that part of current version was written by Gao E. There is a heart breaking story saying that after Cao Xueqin died, Cao‘s wife burned the last 40 chapter manuscript for heating because she was desperately poor. This story was proved a rumor a couple of days ago because someone found several pages of the original last 40 chapters written by Cao.
In the novel, Wang Xifeng was in charge of Da Guan Yuan, where people of Jia family lived. It was mentioned in the newly recovered pages that Wang Xifeng used to arrange rooms for Jia Baoyu, Lin Daiyu, Xue Baochai and other teenagers. Because Jia Baoyu was the most important inheritor of Jia family, and Xue Baochai was beautiful and very capable , Wang Xifeng didn‘t want Jia Baoyu to marry Xue Baochai, in case that Xue Baochai might take her place. So, Wang Xifeng wanted Baoyu‘s room and Baochai‘s room to be located at two ends of a road, and this road should be as long as possible. But Baoyu was very bad at directions, and he demanded that there could be at most one turn along the road from his room to Baochai‘s room, and if there was a turn, that turn must be ninety degree. There is a map of Da Guan Yuan in the novel, and redists (In China English, one whose job is studying 《Dream of the Red Chamber》is call a "redist") are always arguing about the location of Baoyu‘s room and Baochai‘s room. Now you can solve this big problem and then become a great redist.
In the novel, Wang Xifeng was in charge of Da Guan Yuan, where people of Jia family lived. It was mentioned in the newly recovered pages that Wang Xifeng used to arrange rooms for Jia Baoyu, Lin Daiyu, Xue Baochai and other teenagers. Because Jia Baoyu was the most important inheritor of Jia family, and Xue Baochai was beautiful and very capable , Wang Xifeng didn‘t want Jia Baoyu to marry Xue Baochai, in case that Xue Baochai might take her place. So, Wang Xifeng wanted Baoyu‘s room and Baochai‘s room to be located at two ends of a road, and this road should be as long as possible. But Baoyu was very bad at directions, and he demanded that there could be at most one turn along the road from his room to Baochai‘s room, and if there was a turn, that turn must be ninety degree. There is a map of Da Guan Yuan in the novel, and redists (In China English, one whose job is studying 《Dream of the Red Chamber》is call a "redist") are always arguing about the location of Baoyu‘s room and Baochai‘s room. Now you can solve this big problem and then become a great redist.
【Input】
The map of Da Guan Yuan is represented by a matrix of characters ‘.‘ and ‘#‘. A ‘.‘ stands for a part of road, and a ‘#‘ stands for other things which one cannot step onto. When standing on a ‘.‘, one can go to adjacent ‘.‘s through 8 directions: north, north-west, west, south-west, south, south-east,east and north-east.
There are several test cases.
For each case, the first line is an integer N(0<N<=100) ,meaning the map is a N × N matrix.
Then the N × N matrix follows.
The input ends with N = 0.
There are several test cases.
For each case, the first line is an integer N(0<N<=100) ,meaning the map is a N × N matrix.
Then the N × N matrix follows.
The input ends with N = 0.
【Output】
For each test case, print the maximum length of the road which Wang Xifeng could find to locate Baoyu and Baochai‘s rooms. A road‘s length is the number of ‘.‘s it includes. It‘s guaranteed that for any test case, the maximum length is at least 2.
【Sample Input】
3
#.#
##.
..#
3
...
##.
..#
3
...
###
..#
3
...
##.
...
0
【Sample Output】
3
4
3
5
【题意】
给出一张图，‘.‘表示路，‘#‘表示墙，要求找出一条最长的路，只允许转弯一次
【分析】
本题首先应该看到虽然要求是可以向八个方向走，但是由于转弯只能是90°的直角弯，所以上下左右四个方向与另外四个方向是完全独立的。
所以直观的想法是分成两组进行BFS，从起点开始（起点应该为某一条路的尽头），记录下上一个点到达当前点的方向、是否转过弯，每一次向下一个点搜索的方向只有三个，记录沿途的最长距离即可。
这道题的代码写得太朴素了，方向这里写了一次复制了7遍，，，都不好意思贴出来了，，，-_-///
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 5 using namespace std; 6 7 int dx1[4]={-1,1,1,-1}; 8 int dy1[4]={-1,-1,1,1}; 9 int dx2[4]={-1,0,1,0}; 10 int dy2[4]={0,-1,0,1}; 11 int ans; 12 bool ma[110][110]; 13 int num[110][110]; 14 15 bool check(int xx,int yy) 16 { 17 int temp1=0,temp2=0; 18 for (int i=0;i<4;i++) 19 { 20 temp1+=ma[xx+dx1[i]][yy+dy1[i]]; 21 temp2+=ma[xx+dx2[i]][yy+dy2[i]]; 22 } 23 if (temp1>0||temp2>0) return true; 24 else return false; 25 } 26 27 typedef struct nod{ 28 int x,y,fx; 29 bool zw; 30 } node; 31 node q[10010]; 32 33 void doit(int xx,int yy) 34 { 35 int head=1,tail=1; 36 memset(num,0,sizeof(num)); 37 q[head].x=xx; 38 q[head].y=yy; 39 q[head].fx=-1; 40 q[head].zw=false; 41 num[xx][yy]=1; 42 while (head<=tail) 43 { 44 if (ma[q[head].x-1][q[head].y-1]&&num[q[head].x-1][q[head].y-1]==0&&(q[head].fx==-1||q[head].fx==0||q[head].fx==1||q[head].fx==2)) 45 { 46 tail++; 47 q[tail].x=q[head].x-1; 48 q[tail].y=q[head].y-1; 49 if (q[head].fx==0||q[head].fx==-1) 50 { 51 q[tail].fx=0; 52 q[tail].zw=q[head].zw; 53 num[q[tail].x][q[tail].y]=num[q[head].x][q[head].y]+1; 54 if (ans<num[q[tail].x][q[tail].y]) ans=num[q[tail].x][q[tail].y]; 55 } else 56 if (q[head].zw==false) 57 { 58 q[tail].fx=0; 59 q[tail].zw=true; 60 num[q[tail].x][q[tail].y]=num[q[head].x][q[head].y]+1; 61 if (ans<num[q[tail].x][q[tail].y]) ans=num[q[tail].x][q[tail].y]; 62 } else tail--; 63 } 64 if (ma[q[head].x-1][q[head].y+1]&&num[q[head].x-1][q[head].y+1]==0&&(q[head].fx==-1||q[head].fx==0||q[head].fx==1||q[head].fx==3)) 65 { 66 tail++; 67 q[tail].x=q[head].x-1; 68 q[tail].y=q[head].y+1; 69 if (q[head].fx==1||q[head].fx==-1) 70 { 71 q[tail].fx=1; 72 q[tail].zw=q[head].zw; 73 num[q[tail].x][q[tail].y]=num[q[head].x][q[head].y]+1; 74 if (ans<num[q[tail].x][q[tail].y]) ans=num[q[tail].x][q[tail].y]; 75 } else 76 if (q[head].zw==false) 77 { 78 q[tail].fx=1; 79 q[tail].zw=true; 80 num[q[tail].x][q[tail].y]=num[q[head].x][q[head].y]+1; 81 if (ans<num[q[tail].x][q[tail].y]) ans=num[q[tail].x][q[tail].y]; 82 } else tail--; 83 } 84 if (ma[q[head].x+1][q[head].y-1]&&num[q[head].x+1][q[head].y-1]==0&&(q[head].fx==-1||q[head].fx==0||q[head].fx==2||q[head].fx==3)) 85 { 86 tail++; 87 q[tail].x=q[head].x+1; 88 q[tail].y=q[head].y-1; 89 if (q[head].fx==2||q[head].fx==-1) 90 { 91 q[tail].fx=2; 92 q[tail].zw=q[head].zw; 93 num[q[tail].x][q[tail].y]=num[q[head].x][q[head].y]+1; 94 if (ans<num[q[tail].x][q[tail].y]) ans=num[q[tail].x][q[tail].y]; 95 } else 96 if (q[head].zw==false) 97 { 98 q[tail].fx=2; 99 q[tail].zw=true;100 num[q[tail].x][q[tail].y]=num[q[head].x][q[head].y]+1;101 if (ans<num[q[tail].x][q[tail].y]) ans=num[q[tail].x][q[tail].y];102 } else tail--;103 104 }105 if (ma[q[head].x+1][q[head].y+1]&&num[q[head].x+1][q[head].y+1]==0&&(q[head].fx==-1||q[head].fx==1||q[head].fx==2||q[head].fx==3))106 {107 tail++;108 q[tail].x=q[head].x+1;109 q[tail].y=q[head].y+1;110 if (q[head].fx==3||q[head].fx==-1) 111 {112 q[tail].fx=3;113 q[tail].zw=q[head].zw;114 num[q[tail].x][q[tail].y]=num[q[head].x][q[head].y]+1;115 if (ans<num[q[tail].x][q[tail].y]) ans=num[q[tail].x][q[tail].y];116 } else 117 if (q[head].zw==false)118 {119 q[tail].fx=3;120 q[tail].zw=true;121 num[q[tail].x][q[tail].y]=num[q[head].x][q[head].y]+1;122 if (ans<num[q[tail].x][q[tail].y]) ans=num[q[tail].x][q[tail].y];123 } else tail--;124 }125 head++;126 }127 128 head=1;tail=1;129 memset(num,0,sizeof(num));130 num[xx][yy]=1;131 while (head<=tail)132 {133 if (ma[q[head].x-1][q[head].y]&&num[q[head].x-1][q[head].y]==0&&(q[head].fx==-1||q[head].fx==0||q[head].fx==1||q[head].fx==2))134 {135 tail++;136 q[tail].x=q[head].x-1;137 q[tail].y=q[head].y;138 if (q[head].fx==0||q[head].fx==-1) 139 {140 q[tail].fx=0;141 q[tail].zw=q[head].zw;142 num[q[tail].x][q[tail].y]=num[q[head].x][q[head].y]+1;143 if (ans<num[q[tail].x][q[tail].y]) ans=num[q[tail].x][q[tail].y];144 } else 145 if (q[head].zw==false)146 {147 q[tail].fx=0;148 q[tail].zw=true;149 num[q[tail].x][q[tail].y]=num[q[head].x][q[head].y]+1;150 if (ans<num[q[tail].x][q[tail].y]) ans=num[q[tail].x][q[tail].y];151 } else tail--;152 }153 if (ma[q[head].x][q[head].y-1]&&num[q[head].x][q[head].y-1]==0&&(q[head].fx==-1||q[head].fx==0||q[head].fx==1||q[head].fx==3))154 {155 tail++;156 q[tail].x=q[head].x;157 q[tail].y=q[head].y-1;158 if (q[head].fx==1||q[head].fx==-1) 159 {160 q[tail].fx=1;161 q[tail].zw=q[head].zw;162 num[q[tail].x][q[tail].y]=num[q[head].x][q[head].y]+1;163 if (ans<num[q[tail].x][q[tail].y]) ans=num[q[tail].x][q[tail].y];164 } else 165 if (q[head].zw==false)166 {167 q[tail].fx=1;168 q[tail].zw=true;169 num[q[tail].x][q[tail].y]=num[q[head].x][q[head].y]+1;170 if (ans<num[q[tail].x][q[tail].y]) ans=num[q[tail].x][q[tail].y];171 } else tail--;172 }173 if (ma[q[head].x][q[head].y+1]&&num[q[head].x][q[head].y+1]==0&&(q[head].fx==-1||q[head].fx==0||q[head].fx==2||q[head].fx==3))174 {175 tail++;176 q[tail].x=q[head].x;177 q[tail].y=q[head].y+1;178 if (q[head].fx==2||q[head].fx==-1) 179 {180 q[tail].fx=2;181 q[tail].zw=q[head].zw;182 num[q[tail].x][q[tail].y]=num[q[head].x][q[head].y]+1;183 if (ans<num[q[tail].x][q[tail].y]) ans=num[q[tail].x][q[tail].y];184 } else 185 if (q[head].zw==false)186 {187 q[tail].fx=2;188 q[tail].zw=true;189 num[q[tail].x][q[tail].y]=num[q[head].x][q[head].y]+1;190 if (ans<num[q[tail].x][q[tail].y]) ans=num[q[tail].x][q[tail].y];191 } else tail--;192 193 }194 if (ma[q[head].x+1][q[head].y]&&num[q[head].x+1][q[head].y]==0&&(q[head].fx==-1||q[head].fx==1||q[head].fx==2||q[head].fx==3))195 {196 tail++;197 q[tail].x=q[head].x+1;198 q[tail].y=q[head].y;199 if (q[head].fx==3||q[head].fx==-1) 200 {201 q[tail].fx=3;202 q[tail].zw=q[head].zw;203 num[q[tail].x][q[tail].y]=num[q[head].x][q[head].y]+1;204 if (ans<num[q[tail].x][q[tail].y]) ans=num[q[tail].x][q[tail].y];205 } else 206 if (q[head].zw==false)207 {208 q[tail].fx=3;209 q[tail].zw=true;210 num[q[tail].x][q[tail].y]=num[q[head].x][q[head].y]+1;211 if (ans<num[q[tail].x][q[tail].y]) ans=num[q[tail].x][q[tail].y];212 } else tail--;213 }214 head++;215 }216 }217 218 int main()219 {220 //freopen("C1003.txt","r",stdin);221 222 int n;223 scanf("%d",&n);224 while (n)225 {226 getchar();227 memset(ma,0,sizeof(ma));228 for (int i=1;i<=n;i++)229 {230 for (int j=1;j<=n;j++)231 {232 char c;233 scanf("%c",&c);234 if (c==‘.‘) ma[i][j]=true;235 }236 getchar();237 }238 239 ans=0;240 for (int i=1;i<=n;i++)241 for (int j=1;j<=n;j++)242 if (ma[i][j]&&check(i,j)) doit(i,j);243 244 printf("%d\n",ans);245 scanf("%d",&n);246 }247 248 return 0;249 }
【D】
Saving Tang Monk
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
【Problem Description】
《Journey to the West》(also 《Monkey》) is one of the Four Great Classical Novels of Chinese literature. It was written by Wu Cheng‘en during the Ming Dynasty. In this novel, Monkey King Sun Wukong, pig Zhu Bajie and Sha Wujing, escorted Tang Monk to India to get sacred Buddhism texts.
During the journey, Tang Monk was often captured by demons. Most of demons wanted to eat Tang Monk to achieve immortality, but some female demons just wanted to marry him because he was handsome. So, fighting demons and saving Monk Tang is the major job for Sun Wukong to do.
Once, Tang Monk was captured by the demon White Bones. White Bones lived in a palace and she cuffed Tang Monk in a room. Sun Wukong managed to get into the palace. But to rescue Tang Monk, Sun Wukong might need to get some keys and kill some snakes in his way.
The palace can be described as a matrix of characters. Each character stands for a room. In the matrix, ‘K‘ represents the original position of Sun Wukong, ‘T‘ represents the location of Tang Monk and ‘S‘ stands for a room with a snake in it. Please note that there are only one ‘K‘ and one ‘T‘, and at most five snakes in the palace. And, ‘.‘ means a clear room as well ‘#‘ means a deadly room which Sun Wukong couldn‘t get in.
There may be some keys of different kinds scattered in the rooms, but there is at most one key in one room. There are at most 9 kinds of keys. A room with a key in it is represented by a digit(from ‘1‘ to ‘9‘). For example, ‘1‘ means a room with a first kind key, ‘2‘ means a room with a second kind key, ‘3‘ means a room with a third kind key... etc. To save Tang Monk, Sun Wukong must get ALL kinds of keys(in other words, at least one key for each kind).
For each step, Sun Wukong could move to the adjacent rooms(except deadly rooms) in 4 directions(north, west, south and east), and each step took him one minute. If he entered a room in which a living snake stayed, he must kill the snake. Killing a snake also took one minute. If Sun Wukong entered a room where there is a key of kind N, Sun would get that key if and only if he had already got keys of kind 1,kind 2 ... and kind N-1. In other words, Sun Wukong must get a key of kind N before he could get a key of kind N+1 (N>=1). If Sun Wukong got all keys he needed and entered the room in which Tang Monk was cuffed, the rescue mission is completed. If Sun Wukong didn‘t get enough keys, he still could pass through Tang Monk‘s room. Since Sun Wukong was a impatient monkey, he wanted to save Tang Monk as quickly as possible. Please figure out the minimum time Sun Wukong needed to rescue Tang Monk.
During the journey, Tang Monk was often captured by demons. Most of demons wanted to eat Tang Monk to achieve immortality, but some female demons just wanted to marry him because he was handsome. So, fighting demons and saving Monk Tang is the major job for Sun Wukong to do.
Once, Tang Monk was captured by the demon White Bones. White Bones lived in a palace and she cuffed Tang Monk in a room. Sun Wukong managed to get into the palace. But to rescue Tang Monk, Sun Wukong might need to get some keys and kill some snakes in his way.
The palace can be described as a matrix of characters. Each character stands for a room. In the matrix, ‘K‘ represents the original position of Sun Wukong, ‘T‘ represents the location of Tang Monk and ‘S‘ stands for a room with a snake in it. Please note that there are only one ‘K‘ and one ‘T‘, and at most five snakes in the palace. And, ‘.‘ means a clear room as well ‘#‘ means a deadly room which Sun Wukong couldn‘t get in.
There may be some keys of different kinds scattered in the rooms, but there is at most one key in one room. There are at most 9 kinds of keys. A room with a key in it is represented by a digit(from ‘1‘ to ‘9‘). For example, ‘1‘ means a room with a first kind key, ‘2‘ means a room with a second kind key, ‘3‘ means a room with a third kind key... etc. To save Tang Monk, Sun Wukong must get ALL kinds of keys(in other words, at least one key for each kind).
For each step, Sun Wukong could move to the adjacent rooms(except deadly rooms) in 4 directions(north, west, south and east), and each step took him one minute. If he entered a room in which a living snake stayed, he must kill the snake. Killing a snake also took one minute. If Sun Wukong entered a room where there is a key of kind N, Sun would get that key if and only if he had already got keys of kind 1,kind 2 ... and kind N-1. In other words, Sun Wukong must get a key of kind N before he could get a key of kind N+1 (N>=1). If Sun Wukong got all keys he needed and entered the room in which Tang Monk was cuffed, the rescue mission is completed. If Sun Wukong didn‘t get enough keys, he still could pass through Tang Monk‘s room. Since Sun Wukong was a impatient monkey, he wanted to save Tang Monk as quickly as possible. Please figure out the minimum time Sun Wukong needed to rescue Tang Monk.
【Input】
There are several test cases.
For each case, the first line includes two integers N and M(0 < N <= 100, 0<=M<=9), meaning that the palace is a N×N matrix and Sun Wukong needed M kinds of keys(kind 1, kind 2, ... kind M).
Then the N × N matrix follows.
The input ends with N = 0 and M = 0.
For each case, the first line includes two integers N and M(0 < N <= 100, 0<=M<=9), meaning that the palace is a N×N matrix and Sun Wukong needed M kinds of keys(kind 1, kind 2, ... kind M).
Then the N × N matrix follows.
The input ends with N = 0 and M = 0.
【Output】
For each test case, print the minimum time (in minutes) Sun Wukong needed to save Tang Monk. If it‘s impossible for Sun Wukong to complete the mission, print "impossible"(no quotes).
【Sample Input】
3 1
K.S
##1
1#T
3 1
K#T
.S#
1#.
3 2
K#T
.S.
21.
0 0
【Sample Output】
5
impossible
8
【题意】
又是一道地图题，题目要求为从起点（悟空的位置）出发，按顺序通过m个点，最后到达终点（唐僧的位置），最后输出impossible或者全程的最短距离。
【分析】
当时看到题目就傻了好久，需要处理的问题太多：
1.钥匙可能有多把，即地图上好多个1，好多个2......
2.蛇的问题，刚开始看的时候还没觉得什么，以为标记一下经过的时候时间+1即可，后来发现有点不对，看了比赛时其他人的提问才知道原来我觉得不对的地方是真不对，有蛇的点经过一次之后蛇就会被杀死！！下次再经过就成了普通点！！
首先解决第一个问题，BFS搜距离+DFS选择路径：
这张图的大小最大只有100*100，总点数最大是10000，考虑最坏情况，即图中的所有点中都有钥匙，9种钥匙均匀分布大约是（9998/9=1110），然后1000^9是......///-_-///......妈蛋，当时没考虑这么多，现在想想这么大的数据量这么做真是早就爆了......
我把所有钥匙相同的点都编为1组，然后用BFS搜出相邻两组所有点对之间的距离，最后从起点（第0组）开始，DFS找出到达终点（第m+1组）的路径。
接下来是第二个更加棘手的情况：
分析下面这张图：
1 K....2 .....3 ..s..4 .....5 ....T
从左上角到达右下角每一点的距离：
1 012342 123453 235564 345675 45678
发现一个重要规律！即如果能够不走有蛇的点，那么一定能找出一条同样短的路不经过有蛇点。也就是说，若是最短路中经过了有蛇点，那么这个点是必定要走的，否则另外找一条路花费的代价会比消灭这条蛇的1点时间更大，即例如出现下面这种情况。
1 K....2 .....3 #S##.4 .....5 T....
穿越蛇点的代价肯定比绕开走要小。
然后看到题目特别指出最多只会出现5条蛇，于是就有了我下面的尝试算法：
1.将所有的蛇拿掉，做一次BFS+DFS操作，得到一个完成全程的最短距离ans；
2.放上一条蛇（把那个点标记为耗时2），再做一次BFS+DFS操作，得到一个完成全程的最短距离ans0。若ans0比ans更大，说明这个有蛇点是必须要经过的，ans+1，拖ans0与ans相等则说明该点可以不经过，不影响结果；
3.拿掉之前的那条蛇，放上下一条蛇，并依此完成以上操作，判断每一个有蛇点是否都是必须经过的，不断ans+1即可。
The 2014 ACMICPC Asia Regional Guangzhou Online
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。