网站建设 方案书,深圳注册公司推荐,wordpress 导航页面模板,wordpress 3.9.2题目 做题过程
注#xff1a;黄色高亮表示需要注意的地方#xff0c;蓝色粗体表示代码思路 好久没有写过代码了#xff0c;今天做这道编程题#xff0c;简直是灾难现场。 上午编程完后发现样例没有通过#xff0c;检查发现算法思路出现了问题#xff1a;我计数了S不能到…题目 做题过程
注黄色高亮表示需要注意的地方蓝色粗体表示代码思路 好久没有写过代码了今天做这道编程题简直是灾难现场。 上午编程完后发现样例没有通过检查发现算法思路出现了问题我计数了S不能到达的格子。【要重视题目中的所有条件特别时限制条件】 中午吃完饭后重新整理了思路使用DFS分别标记可以从S出发到达的格子和可以到达T的格子两种标记分别放在F1和F2数组中其中1表示标记。 接下来又遇到了编译错误的问题借鉴网上的说法直接再代码前加入一下万能引入便通过了 #include bits/stdc.h using namespace std; 编译通过后系统显示我只有10分我检查了代码的思路使用各种样例检查也没有问题。我自己写了个生成随机样例的代码 #includebits/stdc.h
using namespace std;#define R 50
#define C 50int main(){//随机生成地图 char M[8]{,.,,|,,-,,#};char a[R][C];srand((unsigned int)time(NULL));for(int i 0; i R; i)for(int j 0; j C; j)a[i][j]M[rand() % 8];srand((unsigned int)time(NULL));a[rand() % R][rand() % C] S;a[rand() % R][rand() % C] T;//输出到文件 FILE* fp fopen(C:/Users/kaoyan/Desktop/test.txt, w);fprintf(fp,%d %d\n,R, C); for(int i 0; i R; i){for(int j 0; j C; j)fprintf(fp,%c,a[i][j]);fprintf(fp,\n);}fclose(fp);return 0;
}我在dev-c尝试了很多次都没有问题这使我很烦恼。纠结了一下午。 吃完晚饭后我仔细想了想那么多样例都没有问题我的代码应该时没有问题的而代码在dev-c上运行和提交到系统运行的区别就在于输入不同我便去检查了输入那部分的代码。我尝试去注释掉fflush(stdin);后再提交惊奇地发现时满分o(▽)ブ 我想这可能是因为系统后台是不标准输入至于避免回车换行地读入只需要在后面的scanf中加上空格就行scanf( %c,MAP i); 代码
#include bits/stdc.h
using namespace std;int R, C, S, T; //S记录开始位置, T记录目标位置
char *MAP; //地图
char *F1; //非0格子表示可以从起点S到达的格子
char *F2; //非0格子表示可以到达目T的格子 //从格子G是否可以上移
bool CanUp(int G){if(G-C0 MAP[G-C]!# (MAP[G]||MAP[G]S||MAP[G]T||MAP[G]|))return true;elsereturn false;
}//从格子G是否可以下移
bool CanDown(int G){if(GCR*C MAP[GC]!# (MAP[G]||MAP[G]S||MAP[G]T||MAP[G]|||MAP[G].))return true;elsereturn false;
}//从格子G是否可以左移
bool CanLeft(int G){if(G%C0 MAP[G-1]!# (MAP[G]||MAP[G]S||MAP[G]T||MAP[G]-))return true;elsereturn false;
}//从格子G是否可以右移
bool CanRight(int G){if(G%CC-1 MAP[G1]!# (MAP[G]||MAP[G]S||MAP[G]T||MAP[G]-))return true;elsereturn false;
}//递归遍历可以从G到达的邻居并更改F1
void ToNeighbor(int G){int n;//邻居位置//向上走 n G - C; if(!F1[n] CanUp(G)){F1[n] 1;ToNeighbor(n);}//向下走 n G C; if(!F1[n] CanDown(G)){F1[n] 1;ToNeighbor(n);}//向左走 n G - 1; if(!F1[n] CanLeft(G)){F1[n] 1;ToNeighbor(n);}//向右走 n G 1; if(!F1[n] CanRight(G)){F1[n] 1;ToNeighbor(n);}
}//递归遍历可以到达G的邻居并更改F2
void FromNeighbor(int G){int n;//邻居位置//判断上邻居n G - C;if(n 0 MAP[n] ! # !F2[n] CanDown(n)){F2[n] 1;FromNeighbor(n);}//判断下邻居n G C;if(n R*C MAP[n] ! # !F2[n] CanUp(n)){F2[n] 1;FromNeighbor(n);}//判断左邻居n G - 1;if(G%C 0 MAP[n] ! # !F2[n] CanRight(n)){F2[n] 1;FromNeighbor(n);}//判断右邻居n G 1;if(G%C C-1 MAP[n] ! # !F2[n] CanLeft(n)){F2[n] 1;FromNeighbor(n);}
}int main(){//初始化 scanf(%d%d,R,C); //fflush(stdin);MAP (char*)malloc(sizeof(char) * R * C);F1 (char*)malloc(sizeof(char) * R * C);F2 (char*)malloc(sizeof(char) * R * C);for(int i 0; i R * C; i){scanf( %c,MAP i);if(MAP[i] S)S i;if(MAP[i] T)T i;F1[i] 0;F2[i] 0; }//填充F1非0格子表示可以从起点到达的格子 F1[S] 1;ToNeighbor(S);//递归遍历可以从S到达的格子并更改F1 //填充F2非0格子表示可以到达目的的格子 F2[T] 1;FromNeighbor(T);//递归遍历可以到达的T的格子并更改F1 if(!F1[T]){//从S不能到达T printf(Im stuck!);return 0;}//计数有特征的格子个数int q 0;for(int i 0; i R*C; i)if(F1[i] 1 F2[i] 0)q;printf(%d,q);return 0;
}
