P 1443ロゴマの遍歴
3379 ワード
タイトルの説明
n*mの碁盤があります(1
にゅうしゅつりょくけいしき
入力形式:
1行4つのデータ、碁盤の大きさ、馬の座標
出力フォーマット:
1つのn*mの行列は、馬がある点に到達するのに少なくとも数歩歩かなければならないことを表す(左揃え、幅5格子、到達できない場合は出力-1)
入出力サンプル
サンプル#1を入力:
3 3 1 1
出力サンプル#1:
0 3 2
3 -1 1
2 1 4
この問題は馬の8種類の歩き方をはっきりさせるだけでいいので、bfsですぐにできました.最後の出力フォーマットに注意してください.
#include
#include
#include
#include
#include
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
struct node{
int x;
int y;
int step;
};
queue q;
int n,m,x,y;
int map[500][500],vis[500][500];
bool ok(node u)
{
if(u.x>=1&&u.x<=n&&u.y>=1&&u.y<=m&&vis[u.x][u.y]!=1)
{
return true;
}else
{
return false;
}
}
void f(node v,node p)
{
if(ok(v))
{
v.step=p.step+1;
vis[v.x][v.y]=1;
map[v.x][v.y]=v.step;
q.push(v);
}
}
void bfs(int x,int y)
{
node p;
p.x=x,p.y=y,p.step=0;
map[x][y]=0;
vis[x][y]=1;
q.push(p);
while(!q.empty())
{
node p=q.front();
q.pop();
node v;
v.x=p.x-1;
v.y=p.y+2;
f(v,p);
v=p;
v.x=p.x+1;
v.y=p.y+2;
f(v,p);
v=p;
v.x=p.x-2;
v.y=p.y-1;
f(v,p);
v=p;
v.x=p.x-2;
v.y=p.y+1;
f(v,p);
v=p;
v.x=p.x+2;
v.y=p.y-1;
f(v,p);
v=p;
v.x=p.x+2;
v.y=p.y+1;
f(v,p);
v=p;
v.x=p.x-1;
v.y=p.y-2;
f(v,p);
v=p;
v.x=p.x+1;
v.y=p.y-2;
f(v,p);
}
}
int main(int argc, char *argv[]) {
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
map[i][j]=-1;
}
}
memset(vis,0,sizeof(vis));
cin>>x>>y;
bfs(x,y);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
//cout<