当前位置: 代码迷 >> 综合 >> Q8.2
  详细解决方案

Q8.2

热度:91   发布时间:2024-01-15 21:20:49.0
#include <iostream>
using namespace std;/* 第一问 
int N;
int pathNum = 0;void dfs(int x, int y)
{if(x == N && y == N){pathNum++;return;}	if(x + 1 <= N)dfs(x + 1, y);if(y + 1 <= N)dfs(x, y + 1);
}int main(void)
{N = 3;dfs(0, 0);cout << pathNum << endl;	return 0;
}
*/
const int maxn = 100;struct node
{int x, y;
};node prenode[maxn][maxn]; int graph[maxn][maxn];
node path[maxn];
int M, N, pathNum = 0;void init()
{memset(graph, false, sizeof(graph));memset(path, 0, sizeof(path));memset(prenode, 0, sizeof(prenode));
}void creat()
{cin >> M >> N;for(int i = 1; i <= M; ++i)for(int j = 1; j <= N; ++j)cin >> graph[i][j];
}void printpath(node pre)
{if(pre.x == 1 && pre.y == 1){cout << pre.x << " " << pre.y << endl;return;}printpath(prenode[pre.x][pre.y]);cout << pre.x << " " << pre.y << endl;	
}void dfs(int x, int y)
{if(graph[x][y] == 0)return;node tmp; tmp.x = x; tmp.y = y;if(x == M && y == N){pathNum++;cout << "The " << pathNum << ":" << endl;printpath(tmp);cout << endl;return;}if(x + 1 <= M){prenode[x + 1][y] = tmp;dfs(x + 1, y);}if(y + 1 <= N){prenode[x][y + 1] = tmp;dfs(x, y + 1);}}int main(void)
{freopen("1.txt", "r", stdin);init();creat();dfs(1, 1);  return 0;
}

  相关解决方案