[UVA][搜索] 10582 - ASCII Labyrinth
Problem B: ASCII Labyrinth
We are trying to construct a labyrinth on a board of sizem × n. Initially, on each square of the board wefind a piece of thin plywood of size 1 × 1 with one of thefollowing three patterns painted on it.
While constructing the labyrinth we may turn the pieces arbitrarilybut each piece must exactly cover a square of the board. We are notallowed to move a piece to another square of the grid.
Given an initial board covered with the pieces, we would like to turnthe pieces in such a way that the patterns on the pieces form at leastone polygonal curve connecting the top left corner square of the boardwith the bottom right square of the board. The picture below presentsan initial state of a board of size 4 × 6 and a labyrinthconstructed from the board in which the above stated goal has beenachieved.
Your task is to read a description of the initial board with thepieces placed on it and to decide whether one can turn the pieces insuch a way that the patterns form a line connecting some edge of thetop left square and some edge of the bottom right square of the board.
The first line of input contains a number c giving the numberof cases that follow. The test data for each case start with twonumbers m and n giving the number of rows and columns onthe board. The remaining lines form an ASCII rendition of the initialboard with the pieces placed on squares. The characters used in therendition are +, -, |, * andspace. See the sample input for the format. The size of the inputboard will be such that m × n ≤ 64.
For each case print in a single line how many different paths exist in the solutionsto the labyrinth problem in the format shown below.
Sample input
1 4 6 +---+---+---+---+---+---+ | | | | | | | |***|***|** |** |** |***| | | | * | * | * | | +---+---+---+---+---+---+ | | | | | | | | |** |** |***|** |** | | | * | * | | * | * | +---+---+---+---+---+---+ | | | | | | | |***|** |***|***|***|** | | | * | | | | * | +---+---+---+---+---+---+ | | | | | | | |** | |***| |** |** | | * | | | | * | * | +---+---+---+---+---+---+Output for sample input
Number of solutions: 2
Author: P. Rudnicki
題目輸入只會有三種。
然後左上跟右下也是可以旋轉的。
只要到得了就好。
寫法分兩種狀況討論，水平跟垂直，遇到拐彎的就會從水平便垂直，垂直變水平。
#include <stdio.h>
int n, m, way = 0;
int g[65][65], used[65][65];
void dfs(int x, int y, int d) {// 0 up-down, 1 left-right
if(x == n-1 && y == m-1) {
way++;
return;
}
used[x][y] = 1;
if(d == 0) {
if(x-1 < 0 || used[x-1][y] || g[x-1][y] == 0) {}
else {
if(g[x-1][y] == 1)
dfs(x-1, y, 0);
else
dfs(x-1, y, 1);
}
if(x+1 >= n || used[x+1][y] || g[x+1][y] == 0) {}
else {
if(g[x+1][y] == 1)
dfs(x+1, y, 0);
else
dfs(x+1, y, 1);
}
} else {
if(y-1 < 0 || used[x][y-1] || g[x][y-1] == 0) {}
else {
if(g[x][y-1] == 1)
dfs(x, y-1, 1);
else
dfs(x, y-1, 0);
}
if(y+1 >= m || used[x][y+1] || g[x][y+1] == 0) {}
else {
if(g[x][y+1] == 1)
dfs(x, y+1, 1);
else
dfs(x, y+1, 0);
}
}
used[x][y] = 0;
}
int main() {
int testcases;
int i, j, k;
char s[4][500];
scanf("%d", &testcases);
while(testcases--) {
scanf("%d %d", &n, &m);
while(getchar() != '\n');
while(getchar() != '\n');
for(i = 0; i < n; i++) {
for(j = 0; j < 4; j++)
gets(s[j]);
for(j = 0, k = 1; j < m; j++, k += 4) {
if(s[1][k] == ' ')
g[i][j] = 0;
else if(s[1][k+2] == '*') // ***
g[i][j] = 1;
else
g[i][j] = 2;
}
}
way = 0;
dfs(0, 0, 0);
dfs(0, 0, 1);
printf("Number of solutions: %d\n", way);
}
return 0;
}