think: 1題目似乎沒有很明顯的模板性，我是否應該反思轉換學習圖的方法，自己目前的認識水平這個題目很難找到DFS與BFS的影子，自己應該把思維延伸，將DFS與BFS的思想運用到解題中，而不是急于求成，越是急于求成，根基越是不牢，最后只會導致自己寸步難行，既然自己在學習圖的存儲結構中決定展現自己的做題風格，那么自己越是艱難越不能盲目做題， 題目說每次可以往上下左右四個方向移動也就意味著每在一個有效位置最多可有4種選擇方案，從一個點移動到另一個點是否意味著更適合深度優先搜索，而對于從一個點回到這個點，是否意味著更適合廣度優先搜索，深度優先搜索的思想是否又與遞歸思想有著千絲萬縷的關系呢？為廣度優先搜索的思想是否又與隊列思想有著千絲萬縷的關系呢？不斷摸索，更要不斷反思總結，只有這樣才能進步
sdut原題鏈接
走迷宮 Time Limit: 1000MS Memory Limit: 65536KB
PRoblem Description 一個由n * m 個格子組成的迷宮，起點是(1, 1)， 終點是(n, m)，每次可以向上下左右四個方向任意走一步，并且有些格子是不能走動，求從起點到終點經過每個格子至多一次的走法數。
Input 第一行一個整數T 表示有T 組測試數據。(T <= 110) 對于每組測試數據: 第一行兩個整數n, m，表示迷宮有n * m 個格子。(1 <= n, m <= 6, (n, m) !=(1, 1) ) 接下來n 行，每行m 個數。其中第i 行第j 個數是0 表示第i 行第j 個格子可以走，否則是1 表示這個格子不能走，輸入保證起點和終點都是都是可以走的。 任意兩組測試數據間用一個空行分開。
Output 對于每組測試數據，輸出一個整數R，表示有R 種走法。
Example Input 3 2 2 0 1 0 0 2 2 0 1 1 0 2 3 0 0 0 0 0 0
Example Output 1 0 4
Hint
Author
以下為accepted代碼
#include <stdio.h>#include <string.h>int a[9][9], visit[9][9];int n, m, flag;void ans(int fn, int fm){ int i, tn, tm; int jn[] = {0, 0, -1, 1}; int jm[] = {-1, 1, 0, 0}; for(i = 0; i < 4; i++) { tn = fn + jn[i]; tm = fm + jm[i]; if(tn == n && tm == m) flag++; else if(tn >= 1 && tn <= n && tm >= 1 && tm <= m) { if(a[tn][tm] == 1 && visit[tn][tm] == 0) { visit[tn][tm] = 1; ans(tn, tm); //visit[tn][tm] = 0; } } } visit[fn][fm] = 0;}int main(){ int T, i, j, x; scanf("%d", &T); while(T--) { flag = 0; memset(a, 0, sizeof(a)); memset(visit, 0, sizeof(visit)); scanf("%d %d", &n, &m); for(i = 1; i <= n; i++) { for(j = 1; j <= m; j++) { scanf("%d", &x); if(x == 0) a[i][j] = 1; else a[i][j] = 0; } } visit[1][1] = 1; ans(1, 1); printf("%d/n", flag); } return 0;}/***************************************************User name: Result: AcceptedTake time: 520msTake Memory: 116KBSubmit time: 2017-02-15 18:22:18****************************************************/新聞熱點
疑難解答
