POJ3009解题报告
这道题目上午就弄出来了，但由于当时有点小郁闷，就没有发出来！不是个好习惯呀，拍砖ing...
这道题目最大的特点是：其他的棋盘题都是一步是一步，有固定的走法，但这道题目没有，需要自己来写，来总结，我的代码是：（呵呵，自恋一把！
while(0==mg[temp_row+p[i][1]][temp_col+p[i][0]]||3==mg[temp_row+p[i][1]][temp_col+p[i][0]])//可以到达 |
PS:如果在这个方向上能走，那么就一直走，直到遇到blocks或者到边上（这种情况，不符合题意，所以需要break）为止。
上面这个很重要，还有就是方向的确定，我感觉这个代码已经很智能化了，每一次调用，把这次的方向传给下一次调用，然后下一次就开始利用本次的方向，循环方向一遍。呵呵，因为要循环4个方向，并且初始的方向可以是4个中的任意一个，因此，需要利用模来处理了！鼓掌ing...我怎么这么聪明啊！！
Source Code
| Problem: 3009 | User: omycle | |
| Memory: 252K | Time: 204MS | |
| Language: C++ | Result: Accepted |
- Source Code
#include <iostream>
using namespace std;
int row_height;
int col_width;
/*矩阵默认为－1*/
/*
int mg[6][6]={1 ,0 ,0, 2, 1, 0,\
1, 1, 0 ,0, 0 ,0,\
0, 0, 0 ,0, 0, 3,\
0 ,0 ,0 ,0, 0, 0,\
1 ,0 ,0 ,0, 0, 1,\
0 ,1, 1, 1, 1 ,1};
*/
//int mg[1][6]={1, 0 ,2, 1, 1, 3};
//int mg[1][13]={2, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,3};
int mg[20][20];
int p[4][2]={{0,1},{-1,0},{0,-1},{1,0}};
/*0：南 1:西 2：北 3：东*/
bool ok=false;
int Step=-1;
void Save(int step)
{
if(!ok)
{Step=step;}
else if(Step>step)
{Step=step;}
}
void print()
{
if(ok)
{
if(Step>10)
{printf("-1\n");}
else
printf("%d\n",Step);
}
else
printf("-1\n");
}
void Dfs(int row,int col,int step,int dir)
{
int cou=1;
for(int i=(dir%4);i<4&&cou<=4;i=(i+1)%4)
{
int temp_row=row;
int temp_col=col;
int flag=false;
while(0==mg[temp_row+p[i][1]][temp_col+p[i][0]]||3==mg[temp_row+p[i][1]][temp_col+p[i][0]])//可以到达
{
temp_row+=p[i][1];
temp_col+=p[i][0];
if(mg[temp_row][temp_col]==3)
{
cou++;
Save(step);
// printf("%d",step);
ok=true;
return ;
}
if((temp_row!=row&&(temp_row>=(row_height-1)||temp_row<=0))||\
(temp_col!=col&&(temp_col<=0||temp_col>=(col_width-1))))
{//必须设置这个flag，偶以为非常必要
flag=true;
break;
}
}
if(flag)
{
cou++;
continue;//说明已经出界了！
}
if(step>10)
{
cou++;
return;
}
if(3==mg[temp_row+p[i][1]][temp_col+p[i][0]])//说明已经到达终点了
{
cou++;
Save(step);
// printf("%d",step);
ok=true;
return ;
}
if(temp_row!=row||temp_col!=col)//如果没有改变，那么不能前进
{
mg[temp_row+p[i][1]][temp_col+p[i][0]]=0;
Dfs(temp_row,temp_col,step+1,i+1);//靠，NB吧
mg[temp_row+p[i][1]][temp_col+p[i][0]]=1;//恢复为blocks
}
cou++;
}
}
int main()
{
while(1)
{
Step=-1;
ok=false;
memset(mg,-1,sizeof(mg));
int row=0;
int col=0;
cin>>col_width>>row_height;
if(col_width==0&&row_height==0)
break;
for(int i=0;i<row_height;i++)
{
for(int j=0;j<col_width;j++)
{
cin>>mg[i][j];
if(mg[i][j]==2)
{ row=i;
col=j;
}
}
}
mg[row][col]=0;
Dfs(row,col,1,0);
print();
}
//system("pause");;
return 0;
}
评论
发表评论