问题 A: 城堡问题题目描述如图为一个地堡的地形图。编写一个程序计算城堡一共有多少个房间最大的房间有多大。城堡被分割成 m×nm \times nm×n (n≤50,n≤50)(n \le 50, n \le 50)(n≤50,n≤50) 个方块每个方块可以有 0∼40 \sim 40∼4 面墙。#代表墙壁|和-都表示没有墙壁。不被墙分割的方块连在一起组成一个房间。城堡外围一圈都是墙。1 2 3 4 5 6 7 ############################# 1 # | # | # | | # #####---#####---#---#####---# 2 # # | # # # # # #---#####---#####---#####---# 3 # | | # # # # # #---#########---#####---#---# 4 # # | | | | # # ############################# (图) # Wall | No wall - No wall这里配一个图方便理解输入第一行是两个整数 RRR 和 CCC分别是南北向、东西向的方块数。接下来是一个 RRR 行 CCC 列的整数矩阵每个整数 ppp 描述一个方块0≤p≤500 \le p \le 500≤p≤50。如果用 111 对应西墙222 对应北墙444 对应东墙888 对应南墙则用来描述一个方块的整数其值就是该方块周围每个墙所对应的数字之和。例如某方块有南墙和北墙则描述它的整数就是 28102 8 102810。某方块四面都有墙则描述它的整数就是 1248151 2 4 8 15124815。输入的数据保证城堡至少有两个房间。输出城堡的房间数、城堡中最大房间所包括的方块数。输入输出样例样例输入 #1复制4 7 11 6 11 6 3 10 6 7 9 6 13 5 15 5 1 10 12 7 13 7 5 13 11 10 8 10 12 13样例输出 #1复制5 9这题主要学习如何跳出围墙访问别的房间。#includeiostream #includevector #includealgorithm #includeunordered_map #includequeue using namespace std; int n, m; int dx[4] { 0,0,1,-1 }; int dy[4] { 1,-1,0,0 }; void dfs(int x, int y, int cur, vectorvectorintg, vectorvectorboolvis, vectorvectorintcnt) { if (x 0 || x n || y 0 || y m) return; if (vis[x][y]) return; /* cout ( x , y ) \n; for(int i0;in;i) { for (int j 0;j m;j) cout cnt[i][j] ; cout \n; } cout \n; */ vis[x][y] true; cnt[x][y] cur; if (!(g[x][y] 1)) dfs(x, y - 1, cur, g, vis, cnt); if (!(g[x][y] 2)) dfs(x - 1, y, cur, g, vis, cnt); if (!(g[x][y] 4)) dfs(x, y 1, cur, g, vis, cnt); if (!(g[x][y] 8)) dfs(x 1, y, cur, g, vis, cnt); } int main() { cin n m; vectorvectorintg(n, vectorint(m)); for (int i 0;i n;i) { for (int j 0;j m;j) cin g[i][j]; } vectorvectorboolvis(n, vectorbool(m, false)); vectorvectorintcnt(n, vectorint(m)); int cur 1; //重点学习跳出当前房间的写法 for (int i 0;i n;i) { for (int j 0;j m;j) { if (!vis[i][j]) { dfs(i, j, cur, g, vis, cnt); cur; } } } unordered_mapint, intmp; int maxn 0; for (int i 0;i n;i) { for (int j 0;j m;j) { mp[cnt[i][j]]; } } for (auto e : mp) { maxn max(maxn, e.second); } int len mp.size(); cout len \n maxn; return 0; }问题 B道路题目描述有NNN个城市编号为111 ~ NNN。城市间有NNN条单向道路每条道路连接两个城市有长度和过路费两个属性。Bob 只有KKK块钱他想从城市111走到城市NNN。问最短需要走多长的路。如果到不了NNN输出−1-1−1。其中2≤N≤1002 \le N \le 1002≤不≤1000≤K≤100000 \le K \le 100000≤K≤100001≤R≤100001 \le R \le 100001≤R≤10000每条路的长度为LLL1≤L≤1001 \le L \le 1001≤L≤100每条路的过路费为TTT0≤T≤1000 \le T \le 1000≤T≤100。输入第一行是KKK第二行是NNN第三行是RRR。接下来有RRR行每行有444个整数s,e,L,Ts, e, L, T seLT 表示从城市sss到城市eee有一条单向路可以沿该路从sss走到eee但不能沿该路从eee走到sss其长度是LLL过路费是TTT。输出只有一行就是问题答案。输入输出样例样例输入 #1复制5 6 7 1 2 2 3 2 4 3 3 3 4 2 4 1 3 4 1 4 6 2 1 3 5 2 0 5 4 3 2样例输出 #1复制11这题同样也配个图方便理解先放个超时的代码这份代码完全就是我自己写的整体逻辑没错但是加了剪枝依旧超时。问了一下科技说可以用动态规划或者记忆数组当然最优解是最短路算法图论——最短路Dijkstra算法-CSDN博客。#includeiostream #includevector #includealgorithm using namespace std; const int N 1e3; int money, n, m; struct edge { int node; int len; int cost; }; vectorvectorstruct edgeg(N); int ans 0x3f3f3f; vectorboolvis(N, false); void dfs(int cur, int money, int lenth) { //cout cur cur money money lenth lenth \n; if (cur n) { ans min(ans, lenth); return; } if (lenth ans) return; for (auto e : g[cur]) { if (money - e.cost 0 !vis[e.node]) { vis[e.node] true; dfs(e.node, money - e.cost, lenth e.len); vis[e.node] false; } } } int main() { //总钱数n个点m条边 cin money n m; for (int i 0;i m;i) { int u, v, l, c; cin u v l c; g[u].push_back({ v,l,c }); } vis[1] true; dfs(1, money, 0); if (ans 0x3f3f3f) cout -1; else cout ans; return 0; }最后用记忆化数组解决的。先放一个没什么注释的代码。#includeiostream #includevector #includealgorithm using namespace std; const int N 1e3; int money, n, m; struct edge { int node; int len; int cost; }; vectorvectorstruct edgeg(N); int ans 0x3f3f3f; vectorboolvis(N, false); vectorvectorintmemo(110, vectorint(10010, 0x3f3f3f3f)); void dfs(int cur, int money, int lenth) { //cout cur cur money money lenth lenth \n; if (lenth ans) return; if (lenth memo[cur][money]) return; memo[cur][money] lenth; if (cur n) { ans lenth; return; } for (auto e : g[cur]) { if (money - e.cost 0 !vis[e.node]) { vis[e.node] true; dfs(e.node, money - e.cost, lenth e.len); vis[e.node] false; } } } int main() { //总钱数n个点m条边 cin money n m; for (int i 0;i m;i) { int u, v, l, c; cin u v l c; g[u].push_back({ v,l,c }); } vis[1] true; dfs(1, money, 0); if (ans 0x3f3f3f3f) cout -1; else cout ans; return 0; }再放一个详细注释的代码。#includeiostream #includevector #includealgorithm using namespace std; const int N 1e3; int money, n, m; struct edge { int node; int len;//长度 int cost;//费用 }; vectorvectorstruct edgeg(N); int ans 0x3f3f3f3f; vectorboolvis(N, false); //记忆数组 vectorvectorintmemo(110, vectorint(10010, 0x3f3f3f3f)); void dfs(int cur, int money, int lenth) { //最优性剪枝如果当前路径长度已经超过已知最优解直接返回。 if (lenth ans) return; //☆☆☆记忆化剪枝 // 如果之前到达(cur, money)状态时有更短的路径就返回。 if (lenth memo[cur][money]) return; //否则记录当前状态的最短路径 memo[cur][money] lenth; if (cur n)//到达目标节点n { ans lenth;//更新全局最优解 return; } //对g[cur]中的每条边e进行遍历 for (auto e : g[cur]) { // 条件1: 有足够的钱支付过路费 // 条件2: 目标节点未被访问(防止回路) if (money - e.cost 0 !vis[e.node]) { vis[e.node] true;//标记访问 dfs(e.node, money - e.cost, lenth e.len); vis[e.node] false;//回溯 } } } int main() { //总预算n个点m条边 cin money n m; for (int i 0;i m;i) { int u, v, l, c; cin u v l c; g[u].push_back({ v,l,c }); } vis[1] true;//标记起点为已访问 dfs(1, money, 0);//在节点1有全部钱路径长度为0 if (ans 0x3f3f3f3f) cout -1; else cout ans; return 0; }再放一个动态规划的错误代码有空再回来修正。#includeiostream #includevector #includealgorithm using namespace std; const int N 1e3; int money, n, m; struct edge { int node; int len;//长度 int cost;//费用 }; vectorvectorstruct edgeg(N); int main() { //总预算n个点m条边 cin money n m; for (int i 0;i m;i) { int u, v, l, c; cin u v l c; g[u].push_back({ v,l,c }); } vectorvectorintdp(n 1, vectorint(money 1, 0x3f3f3f3f)); dp[1][0] 0; for (int j 0;j money;j) { for (int i 1;i n;i) { if (dp[i][j] 0x3f3f3f3f) continue; for (auto e : g[i]) { int cur_cost j e.cost; if (cur_cost money) { dp[e.node][cur_cost] min(dp[e.node][cur_cost], dp[i][j] e.len); } } } } int ans 0x3f3f3f3f; for (int i 0;i money;i) ans min(ans, dp[n][i]); if (ans 0x3f3f3f3f) cout -1; else cout ans; return 0; }再放个错误的最短路算法实现的代码有空再改。#includeiostream #includevector #includequeue using namespace std; int INF 0x3f3f3f; struct edge { int node; int val;//len int cost; bool operator (const struct edge other) const { return val other.val; } }; vector struct edge g[2100]; vector bool visited(2100, false); vector int dis(2100, INF); vectorintmon(2100, 0); priority_queue struct edge, vectorstruct edge, greaterstruct edge heap; int main() { int money, n, m; cin money n m; vectorvectorstruct edgeg(n 1); for (int i 0;i m;i) { int u, v, l, c; cin u v l c; g[u].push_back({ v,l,c }); } dis[1] 0; mon[1] money; heap.push({ 1,0,money }); while (!heap.empty()) { auto t heap.top(); heap.pop(); int u t.node; if (visited[u] true) continue; visited[u] true; for (auto e : g[u]) { int v e.node; if (visited[v] false dis[u] e.val dis[v] mon[u] - e.cost 0) { dis[v] dis[u] e.val; heap.push({ v,dis[v],mon[u] - e.cost }); } } } cout dis[n]; return 0; }问题 C: 马走日题目描述马在中国象棋中以日字规则移动。编写一段程序给定 n×mn \times mn×m 大小的棋盘 (n10(n \lt 10(n10m10)m \lt 10)m10) 以及马的初始位置 (x,y)(x, y)(x,y)要求不能重复经过棋盘上的同一个点计算马有多少条路径可以遍历棋盘上所有点。输入第一行为整数 TTTT10T \lt 10T10表示测试数据的组数。每一组测试数据包含一行为 444 个整数分别为棋盘的大小以及初始位置坐标 n,m,x,yn, m, x, yn,m,x,y (0≤x≤n−1(0 \le x \le n-1(0≤x≤n−10≤y≤m−10 \le y \le m-10≤y≤m−1m10m \lt 10m10n10)n \lt 10)n10)。输出每组测试数据输出一行为一个整数表示马能遍历棋盘的路径总数000 为无法遍历一次。输入输出样例样例输入 #1复制1 5 4 0 0样例输出 #1复制32问题 D: 棋盘问题题目描述在 n×nn \times nn×n 的国际象棋棋盘上摆放 kkk 个棋子 (n≤8(n \le 8(n≤8, k≤n)k \le n)k≤n)棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘的同一行或者同一列且规定有些位置不能摆放棋子。求所有可行的摆放方案数量。输入输入包含多组测试数据。每组数据的第一行是两个正整数 nnn 和 kkk用一个空格隔开表示将在一个 n×nn \times nn×n 的矩阵内描述棋盘以及摆放棋子的数量。n≤8n \le 8n≤8k≤nk \le nk≤n。当输入为-1 -1时表示输入结束。随后的 nnn 行描述棋盘的形状每行有 nnn 个字符其中#表示棋盘区域.表示空白区域数据保证不出现多余的空白行或者空白列。输出对于每一组数据给出一行输出输出摆放的方案数量 CCC (((数据保证 C231)C \lt 2^{31})C231)。输入输出样例样例输入 #1复制2 1 # . . # 4 4 . . . # . . # . . # . . # . . . -1 -1样例输出 #1复制2 1