晕.
不只你这两组错误数据太多了.继续改.就不信了
不只你这两组错误数据太多了.继续改.就不信了
这是我写的代码,老长了....
确实wa,不过不晓得为什么...
程序代码：
#include<stdio.h>
#define MAX_M 8
#define MAX_N 8
#define INFINITY 300#define UN_CHECKED -1
#define UN_USED -2
#define BLOCK '#'
#define BLANK '.'
#define SMALL_MONSTER 'o'
#define BIG_MONSTER 'O'#define push(x,y,v) disX[y][x] =(v); \
queue[tail][0] =(x); \
queue[tail++][1] =(y);
char map[MAX_N][MAX_M+1];
char pos[MAX_N*MAX_M][2];
int disX[MAX_N][MAX_M];int disB[MAX_N*MAX_M];
//动态规划之用 disT[m][n][k]表示从m到n历经k个节点的最短距离
// distT[m][n][k] =min{disT[m][i][2]+disT[i][n][k-1] ;其中disN[m][n][k-1]中不含i}
int disT[MAX_N*MAX_M][MAX_N*MAX_M][MAX_N*MAX_M];
//动态规划之用 dist[m][n][k][..]表示记录从m到n经历的节点
char disN[MAX_N*MAX_M][MAX_N*MAX_M][MAX_N*MAX_M][MAX_N*MAX_M];
char queue[MAX_N*MAX_M][2];void calculateDist(int sx,int sy,int width,int height){
int head =0,tail =0,d;
push(sx,sy,0);
while(head<tail){
sx =queue[head][0];
sy =queue[head++][1];
d =disX[sy][sx];
if(sy-1>=0&&disX[sy-1][sx]==UN_CHECKED){
push(sx,sy-1,d+1);
}
if(sy+1<height&&disX[sy+1][sx]==UN_CHECKED){
push(sx,sy+1,d+1);
}
if(sx-1>=0&&disX[sy][sx-1]==UN_CHECKED){
push(sx-1,sy,d+1);
}
if(sx+1<width&&disX[sy][sx+1]==UN_CHECKED){
push(sx+1,sy,d+1);
}
}
}
//将BIG Monster设为block
void translateA(int width,int height){
for(int y =0;y<height;y++)
for(int x =0;x<width;x++)
if(map[y][x]==BLOCK||map[y][x]==BIG_MONSTER) disX[y][x] =UN_USED;
else disX[y][x] =UN_CHECKED;
}
//将big monster设为blank
void translateB(int width,int height){
for(int y =0;y<height;y++)
for(int x =0;x<width;x++)
if(map[y][x]==BLOCK) disX[y][x] =UN_USED;
else disX[y][x] =UN_CHECKED;
}
//计算小鬼到终点的距离
void calculateDistB(int width,int height,int smallCount){
for(int index=0;index<smallCount;index++){
translateB(width,height);
calculateDist(pos[index][0],pos[index][1],width,height);
disB[index] =disX[height-1][width-1]>=0?disX[height-1][width-1]:INFINITY;
}
}
//计算任意两个小鬼的最短距离
void calculateDistA(int width,int height,int smallCount){
for(int index=0;index<smallCount;index++){
translateA(width,height);
calculateDist(pos[index][0],pos[index][1],width,height);
for(int p =0;p<smallCount;p++){
disT[index][p][2] =disX[pos[p][1]][pos[p][0]]>=0?disX[pos[p][1]][pos[p][0]]:INFINITY;
disN[index][p][2][0] =index;
disN[index][p][2][1] =p;
}
}
}
//...
void dp(int width,int height,int smallCount,int num){
for(int k=3;k<=num;k++)
for(int m=0;m<smallCount;m++)
for(int n=0;n<smallCount;n++){
if(m==n) continue;
disT[m][n][k] =INFINITY;
for(int p=0;p<smallCount;p++){
if(p==m||p==n) continue;
bool flags =true;
for(int index =1;index<k-1;index++)
if(m ==disN[p][n][k-1][index]){
flags =false;
break;
}
if(!flags) continue;
if(disT[m][n][k]>disT[m][p][2]+disT[p][n][k-1]){
disT[m][n][k]=disT[m][p][2]+disT[p][n][k-1];
disN[m][n][k][0] =m;
for(int j=1;j<k;j++) disN[m][n][k][j] =disN[p][n][k-1][j-1];
}
}
}
}
int getPos(int width,int height,int &num){
if(map[0][0]!=SMALL_MONSTER){
map[0][0] =SMALL_MONSTER;
num ++;
}
int count =0;
for(int y=0;y<height;y++)
for(int x=0;x<width;x++)
if(map[y][x] ==SMALL_MONSTER){
pos[count][0] =x;
pos[count][1] =y;
count ++;
}
return count;
}
void readMap(int height){
for(int y =0;y<height;y++) scanf(\"%s\",map[y]);
}int main(){
int width,height,num;
int minDist,smallCount;
while(scanf(\"%d%d%d\",&width,&height,&num)!=EOF){
readMap(height);
if(map[0][0]==BLOCK||(num!=0&&map[0][0]==BIG_MONSTER)){ //这里修改了下
printf(\"-1\n\");
continue;
}
translateA(width,height);
calculateDist(0,0,width,height);
minDist =disX[height-1][width-1]>=0?disX[height-1][width-1]:INFINITY;
smallCount =getPos(width,height,num);
if(smallCount<num){
printf(\"%d\n\",minDist<INFINITY?minDist+1:-1);
continue;
}
else if(num<=1){
translateB(width,height);
calculateDist(0,0,width,height);
printf(\"%d\n\",disX[height-1][width-1]>=0?disX[height-1][width-1]+1:-1);
continue;
}
calculateDistB(width,height,smallCount);
calculateDistA(width,height,smallCount);
dp(width,height,smallCount,num);
for(int index=1;index<smallCount;index++)
if(minDist>disB[index]+disT[0][index][num]) minDist =disB[index]+disT[0][index][num];
printf(\"%d\n\",minDist<INFINITY?minDist+1:-1);
}
}
[此贴子已经被作者于2007-9-15 23:49:19编辑过]
