帮忙测试下 hdu 1010 ！！！！！！！
http://acm.hdu.edu.cn/showproblem.php?pid=1010
帮忙提供错误的测试数据咯，能帮我找出错误更好！！！！！
- C/C++ code
#include<iostream>#include<stack>#include<fstream>////#define INF 100000#define N 51using namespace std;class shortestPath{private: int n;//顶点总数 int u;//入口点 int d;//出口点 int arrTemp[N][N]; int array[N][N]; int weightPath[N][N];public: shortestPath(int arr[N][N], int s, int e, int m){ n = m; u = s; d = e; memset(array, 0, sizeof(array)); memset(arrTemp, 0, sizeof(arrTemp)); memset(weightPath, 0, sizeof(weightPath)); for(int i=0; i<=n; i++)//这个地方可以有好的方法吗？？ for(int j=0; j<n; j++) array[i][j]=arr[i][j]; fun(); } void fun();//算法过程 int getValue();//取u到d的最短路径权值 ~shortestPath(){ };};void shortestPath::fun(){ int queue[N] = {0};//模拟队列 int temp;//中间转储 int flagH=0,flagR=0;//队头与队尾 queue[flagR] = u; flagR++; temp = queue[flagH]; for(int i=0; i<n; i++){//初始化入口点的最短距离 arrTemp[temp][i] = array[temp][i]!=0 ? array[temp][i] : INF; arrTemp[ n ][i] = array[temp][i]!=0 ? array[temp][i] : INF; if(array[temp][i] != INF && temp != i){ queue[flagR] = i; flagR++; } } flagH++; //计算过程中各结点路径最小值 while(flagH < flagR){ temp = queue[flagH]; flagH++; for(int i=0; i<n; i++){ if(array[temp][i] >= INF || temp == i) arrTemp[temp][i] = INF;/////!!!!!!!!! else{ //计算过程路径值 if(arrTemp[i][temp]!= 0){ if(arrTemp[n][temp] - array[temp][i] == arrTemp[n][i] || arrTemp[i][temp] - array[temp][i] == 0) arrTemp[temp][i] = arrTemp[n][temp]; else arrTemp[temp][i] = array[temp][i] + arrTemp[n][temp]; } else arrTemp[temp][i] = array[temp][i] + arrTemp[n][temp]; //重新确定当前结点的最短路径 arrTemp[n][i] = arrTemp[n][i] < arrTemp[temp][i] ? arrTemp[n][i] : arrTemp[temp][i]; //判断当前结点是否需要入栈 int flag = 1; for(int j=0; j<flagR; j++) if(i == queue[j]){ flag=0; break; } if(flag == 1){ queue[flagR] = i; flagR++; } } } } //确定入口点到各点的最短路径经过的顶点 arrTemp[n][u] = 0; int x=0,k; for(int i=0; i<n; i++){ k=2; if(i == u) continue; weightPath[i][0] = arrTemp[n][i]; weightPath[i][k++] = i; x = i; temp = arrTemp[n][i]; //确定最小路径的终点 while(temp>0){ //确定中间点 for(int j=0; j<n; j++){ if(temp == arrTemp[j][x]){ temp -= array[j][x]; weightPath[i][k++] = j; if(temp == 0){ weightPath[i][k] = u; weightPath[i][1] = k-2; } break; } } for(int h=0; h<n; h++){ if(h == u) continue; if(temp == arrTemp[n][h]) x=h; } } }}int shortestPath::getValue(){ return weightPath[d][0];}int main(){ ifstream cin("hdu.txt");//// int n, m, t; char a[10][10]; int start[2], door[2]; while(cin>>n>>m>>t && (n!=0||m!=0||t!=0)){ int g[N][N] = {0}; for(int i=0; i<n; i++) for(int j=0; j<m; j++){ cin>>a[i][j]; if(a[i][j]=='S') start[0]=i, start[1]=j; if(a[i][j]=='D') door[0]=i, door[1]=j; } //转换成图的结构 for(int i=0; i<n; i++){ for(int j=0; j<m; j++){ if(a[i][j] != 'X'){ if(a[i-1][j]!='X' && i-1>=0) g[i*m+j][(i-1)*m+j]=1; if(a[i+1][j]!='X' && i+1<n) g[i*m+j][(i+1)*m+j]=1; if(a[i][j-1]!='X' && j-1>=0) g[i*m+j][i*m+j-1]=1; if(a[i][j+1]!='X' && j+1<m) g[i*m+j][i*m+j+1]=1; } } } //将无连接的两个点赋值无穷大 for(int i=0; i<n*m; i++) for(int j=0; j<n*m; j++) if(g[i][j]!=1 && i!=j) g[i][j]=INF; int s=start[0]*m+start[1]; int d=door[0]*m+door[1]; shortestPath hdu(g, s, d, n*m); if(hdu.getValue()<=t) cout<<"YES"<<endl; else cout<<"NO"<<endl; } return 0;}
[解决办法]
那我帮你顶一下吧，呵呵
这是我AC的代码：
- C/C++ code
#include <iostream>#include <cmath>using namespace std;char map[9][9];int n, m, t, dx, dy;bool escape;int dir[4][2] = {{0,-1}, {0,1}, {1,0}, {-1,0}};void Dfs(int sx, int sy, int cnt);int main(){ int i, j, sx, sy; while(cin >> n >> m >> t) { if(0==n && 0==m && 0==t) break; int wall = 0; for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { cin >> map[i][j]; if('S' == map[i][j]) { sx = i; sy = j; } else if('D' == map[i][j]) { dx = i; dy = j; } else if('X' == map[i][j]) wall++; } } if(n*m-wall <= t) { cout << "NO" << endl; continue; } escape = false; map[sx][sy] = 'X'; Dfs(sx, sy, 0); if(escape) cout << "YES" << endl; else cout << "NO" << endl; } return 0;}void Dfs(int sx, int sy, int cnt){ int i, temp; if(sx>n || sx<=0 || sy>m || sy<=0) return; if(cnt==t && sx==dx && sy==dy) escape = true; if(escape) return; temp = (t-cnt) - abs(sx-dx) - abs(sy-dy); if(temp<0 || temp%2==1) return; for(i=0;i<4;i++) { if('X' != map[sx+dir[i][0]][sy+dir[i][1]]) { map[sx+dir[i][0]][sy+dir[i][1]] = 'X'; Dfs(sx+dir[i][0], sy+dir[i][1], cnt+1); map[sx+dir[i][0]][sy+dir[i][1]] = '.'; } } return;}
[解决办法]
请试以下输入:
2 2 3
D.
.S
正确输出是NO,但LZ程序输出YES.请注意题目要求是the doggie had to arrive at the door on exactly the T-th second