题目

做题过程

注：黄色高亮表示需要注意的地方，蓝色粗体表示代码思路

好久没有写过代码了，今天做这道编程题，简直是灾难现场。

上午编程完后发现样例没有通过，检查发现算法思路出现了问题：我计数了S不能到达的格子。【要重视题目中的所有条件，特别时限制条件】
中午吃完饭后重新整理了思路：使用DFS分别标记可以从S出发到达的格子和可以到达T的格子，两种标记分别放在F1和F2数组中，其中1表示标记。

接下来又遇到了编译错误的问题，借鉴网上的说法直接再代码前加入一下万能引入便通过了：
#include <bits/stdc++.h>
using namespace std;

编译通过后，系统显示我只有10分，我检查了代码的思路，使用各种样例检查也没有问题。我自己写了个生成随机样例的代码：

#include<bits/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-C>=0 && MAP[G-C]!='#' && (MAP[G]=='+'||MAP[G]=='S'||MAP[G]=='T'||MAP[G]=='|'))return true;elsereturn false;
}//从格子G是否可以下移
bool CanDown(int G){if(G+C<R*C && MAP[G+C]!='#' && (MAP[G]=='+'||MAP[G]=='S'||MAP[G]=='T'||MAP[G]=='|'||MAP[G]=='.'))return true;elsereturn false;
}//从格子G是否可以左移
bool CanLeft(int G){if(G%C>0 && MAP[G-1]!='#' && (MAP[G]=='+'||MAP[G]=='S'||MAP[G]=='T'||MAP[G]=='-'))return true;elsereturn false;
}//从格子G是否可以右移
bool CanRight(int G){if(G%C<C-1 && MAP[G+1]!='#' && (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("I'm 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;
}