|
发表于 2023-12-1 13:17:09
|
显示全部楼层
你的代码思路正确,不过需要一个注意的地方。
对于此题而言,路径条数可能会达到 O(C(N+M,N)),这个数量是巨大的,其数值已经远远超过了 int 的最大存储范围。所以,你应该使用更大的整数类型来表示答案,例如 C99 中添加的超长 (long long) 类型。
以下是修正后的代码:
- #include <stdio.h>
- int main()
- {
- int bi,bj,n,m;
- scanf("%d %d %d %d",&bi,&bj,&n,&m);
- long long chessboard[30][30] = {0};
-
- for (int i=0;i<=bi;i++){
- for (int j=0;j<=bj;j++){
- chessboard[i][j] = 1;
- }
- }
- chessboard[n][m] = 0;
- if (n-1>=0 && m+2<=bj)chessboard[n-1][m+2]=0;
- if (n+1<=bi && m+2<=bj)chessboard[n+1][m+2]=0;
- if (n-1>=0 && m-2>=0)chessboard[n-1][m-2]=0;
- if (n+1<=bi && m-2>=0)chessboard[n+1][m-2]=0;
- if (n+2<=bi && m+1<=bj)chessboard[n+2][m+1]=0;
- if (n+2<=bi && m-1>=0)chessboard[n+2][m-1]=0;
- if (n-2>=0 && m-1>=0)chessboard[n-2][m-1]=0;
- if (n-2>=0 && m+1<=bj)chessboard[n-2][m+1]=0;
- for (int i=0;i<=bi;i++){
- for (int j=0;j<=bj;j++){
- if (0==i && 0==j){continue;}
- if (chessboard[i][j]==0){
- continue;
- }
- if (i==0){
- chessboard[i][j] = chessboard[i][j-1];
- }
- else if (j==0){
- chessboard[i][j] = chessboard[i-1][j];
- }
- else{
- chessboard[i][j] = chessboard[i][j-1]+chessboard[i-1][j];
- }
- }
- }
- printf("%lld",chessboard[bi][bj]);
-
- return 0;
- }
复制代码
在 OI (信息学竞赛)中,要使用合理的类型来存储结果和变量,超过了变量支持的最大数值则会引发溢出,从而得到错误的结果。 |
|