9017. Amazing MazesConstraints
Time Limit: 1 secs, Memory Limit: 256 MB
Description
You are requested to solve maze problems. Without passing throughthese mazes, you might not be able to pass through the domesticcontest!
A maze here is a rectangular area of a number of squares, lined upboth lengthwise and widthwise, The area is surrounded by walls exceptfor its entry and exit. The entry to the maze is at the leftmost partof the upper side of the rectangular area, that is, the upper side ofthe uppermost leftmost square of the maze is open. The exit islocated at the rightmost part of the lower side, likewise.
In the maze, you can move from a square to one of the squaresadjoining either horizontally or vertically. Adjoining squares,however, may be separated by a wall, and when they are, you cannot gothrough the wall.
Your task is to find the length of the shortest path from the entry tothe exit. Note that there may be more than one shortest paths, orthere may be none.
Input
The input consists of one or more datasets, each of which represents amaze.
The first line of a dataset contains two integer numbers, thewidth w and the height h of the rectangular area, inthis order.
The following 2 × h ? 1 lines of a dataset describewhether there are walls between squares or not. The first line startswith a space and the rest of the line contains w ? 1integers, 1 or 0, separated by a space. These indicate whether wallsseparate horizontally adjoining squares in the first row. An integer1 indicates a wall is placed, and 0 indicates no wall is there. Thesecond line starts without a space and contains w integers, 1 or 0,separated by a space. These indicate whether walls separatevertically adjoining squares in the first and the second rows. Aninteger 1/0 indicates a wall is placed or not. The following linesindicate placing of walls between horizontally and verticallyadjoining squares, alternately, in the same manner.
The end of the input is indicated by a line containing two zeros.
The number of datasets is no more than 100. Both the widths and theheights of rectangular areas are no less than 2 and no more than 30.
Output
For each dataset, output a line having an integer indicating thelength of the shortest path from the entry to the exit. The length ofa path is given by the number of visited squares. If there existsno path to go through the maze, output a line containing a singlezero. The line should not contain any character other than thisnumber.
Sample Input2 3 10 1 01 0 19 4 1 0 1 0 0 0 0 00 1 1 0 1 1 0 0 0 1 0 1 1 0 0 0 00 0 0 0 0 0 0 1 1 0 0 0 1 0 0 1 10 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 012 5 1 0 0 0 0 0 0 0 0 0 00 0 0 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 00 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 1 0 1 0 0 00 0 0 1 1 0 1 1 0 1 1 0 0 0 0 0 0 1 0 0 1 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 00 0Sample Output4020Problem Source
2013年每周一赛第八场 Asia Regional Contest 2010 in Tokyo
建图步骤：
首先要知道，题目中的01单数行表示的是格子，偶数行表示的是墙壁，比如把题目中第三个样例的图建出来看看：
void make_map(int w, int h) {int i, j;memset(map, 0, sizeof(map));for (i = 0; i <= 2 * h; i++) {if (i == 0 || i == 2 * h) {for (j = 0; j <= 2 * w; j++) {map[i][j] = 1;}} else {map[i][0] = map[i][2 * w] = 1;}}map[0][1] = map[2 * h][2 * w – 1] = 0;for (i = 1; i <= 2 * h – 1; i++) {if (i % 2 == 1) {for (j = 0; j < w – 1; j++) {scanf("%d", &map[i][2 * j + 2]);}} else {for (j = 0; j < w; j++) {scanf("%d", &map[i][2 * j + 1]);}}}//以下就是添砖加瓦部分，，注意添砖加瓦只在墙壁行中执行for (i = 2; i < 2 * h; i += 2) {//i保持是偶数，保证修改的是墙壁而不是格子for (j = 1; j < 2 * w; j++) {//两道墙壁中的链接点也设为墙壁if (map[i – 1][j] == 1 && map[i + 1][j] == 1)map[i][j] = 1;if (map[i][j – 1] == 1 && map[i][j + 1] == 1)map[i][j] = 1;}}for (i = 2; i < 2 * h; i += 2) {//把墙角设为墙壁for (j = 1; j < 2 * w; j++) {if (map[i – 1][j] == 1 && map[i][j – 1] == 1)map[i][j] = 1;if (map[i + 1][j] == 1 && map[i][j – 1] == 1)map[i][j] = 1;if (map[i – 1][j] == 1 && map[i][j + 1] == 1)map[i][j] = 1;if (map[i + 1][j] == 1 && map[i][j + 1] == 1)map[i][j] = 1;}}//以上就是添砖加瓦部分exit_i = 2 * h – 1;exit_j = 2 * w – 1;}当去除了添砖加瓦后：
接受失败也等于给了自己从零开始的机会，接受失败更是一种智者的宣言和呐喊;
