0
已解决
高级天翼
3020 道路施工
经验值：1600 时间限制：1000毫秒
题目描述 Description
D城有南北街道a条（由西到东分别编号1~a），东西街道b条(由南向北分别编号1~b)，你住在（1，1）学校在（a，b）最近有几个交叉路口在施工，无法通车，现在只能往右或者往上走，求去上学有多少种走法？
输入描述 Input Description
第一行包含两个整数a和b，并且满足1≤a，b≤16。
第二行包含一个整数N，表示有N个路口在维修(1≤N≤40)。
接下来N行，每行两个整数X_i，Y_i，描述路口的位置。
输出描述 Output Description
输出一个整数表示从(1，1)到(a，b)的行车路线总数。
样例输入 Sample Input
5 4 3 2 2 2 3 4 2
样例输出 Sample Output
5
//CODE
//#pragma GCC optimize(3)
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
using namespace std;
int a, b, n;
int x, y;
int cnt;
int dir[2][2] = {{-1, 0}, {0, 1}};
bool vis[100][100];
bool G[100][100];
void dfs(int ex, int ey) {
if (ex == a && ey == b) {
cnt ++;
}
for (int i = 0; i < 2; i ++) {
int nx = ex + dir[i][0], ny = ex + dir[i][1];
if (nx >= 1 && nx <= a && ny >= 1 && ny <= b && !vis[nx][ny] && !G[nx][ny]) {
vis[nx][ny] = true;
dfs(nx, ny);
vis[nx][ny] = false;
}
}
}
int main() {
// freopen ("题目名.in", "r", stdin);
// freopen ("题目名.out", "w", stdout);
cin >> a >> b;
cin >> n;
for (int i = 1; i <= n; i ++) {
cin >> x >> y;
G[x][y] = true;
}
vis[1][1] = true;
dfs(1, 1);
vis[1][1] = false;
cout << cnt;
// fclose (stdin);
// fclose (stdout);
return 0;//好习惯！
}
为什么输出0
张恩泽在2021-06-04 19:28:22追加了内容
顶！
张恩泽在2021-06-12 21:15:20追加了内容
再顶一下
0
已采纳
中级启示者
边界到了不应该return吗
而且dir数组也错了
const int dir[3][2]={{0,1},{1,0}};
0
资深守护
大哥这是递推
#include <bits/stdc++.h>
using namespace std;
int a,b,n;
bool vis[20][20];
int f[20][20];
int main()
{
cin>>a>>b;
cin>>n;
while(n--)
{
int x, y;
cin>>x>>y;
vis[x][y]=1;
}
f[1][1]=1;
for(int i=1;i<=a;i++)
{
for(int j=1;j<=b;j++)
{
if(vis[i][j]||i==1&&j==1) continue;
else if(i==1) f[i][j]+=f[i][j-1];
else if(j==1) f[i][j]+=f[i-1][j];
else f[i][j]+=f[i][j-1]+f[i-1][j];
}
}
cout<<f[a][b];
return 0;
}
0
缔造者之神
1
