问题标题: 酷町堂：5014

Question

0

已解决

胡景波

中级光能

5014 国际象棋

经验值：0 时间限制：1000毫秒

题目描述 Description

酷町喵和她的小伙伴**国际象棋，国际象棋的棋盘大小为8*8，其中有一个棋子叫做国王（King）。国王可以向上下左右以及斜着的共8个方向走一步。现在棋盘上有的位置被敌人占领不能通过。酷町喵想知道，如果要把国王从现在的一个位置移动到某个位置，一共有多少种可能的路径。将这些路径打印出来。

输入描述 Input Description

第一行，四个空格隔开的整数，sx sy ex ey，(sx,sy)表示起点位置，(ex,ey)表示终点位置
接下来8行，每行8个空格隔开的整数，0表示这个位置可以通过，1表示这个位置不能通过

输出描述 Output Description

前五行，每行一个从起点到终点的路径，国王移动的方向是从正上方开始，顺时针转动，不足5种方案则有多少种打印多少种
第六行，一个整数，表示从起点到终点最多的方案数

样例输入 Sample Input

8 8 3 6 0 0 1 0 1 1 1 0 0 0 0 0 1 1 0 1 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 1 1 0 1 0 1 1 0 1 0 1 0 1 0 0 1 0 1 1 0 0 1 0 1 0 0 0 1 1 0 1 1 0

样例输出 Sample Output

(8,8)->(7,8)->(6,8)->(5,7)->(4,7)->(3,7)->(2,7)->(3,6) (8,8)->(7,8)->(6,8)->(5,7)->(4,7)->(3,7)->(3,8)->(2,7)->(3,6) (8,8)->(7,8)->(6,8)->(5,7)->(4,7)->(3,7)->(4,6)->(3,6) (8,8)->(7,8)->(6,8)->(5,7)->(4,7)->(3,7)->(4,6)->(4,5)->(3,6) (8,8)->(7,8)->(6,8)->(5,7)->(4,7)->(3,7)->(3,6) 735388

#include<iostream>
#include<cstring>
using namespace std;
int nx,ny,fx,fy,vis[10][10],map[10][10],ans,path[105][2],cnt;
int dir[10][2]={{0},{1,0},{-1,0},{0,-1},{0,1},{1,-1},{1,1},{-1,-1},{-1,1}};
void dfs(int x,int y,int bs){
   path[bs][0]=x,path[bs][1]=y;
   if(x==fx&&y==fy){
       ans++;
       if(cnt<=4){
           for(int i=1;i<bs;i++)
               cout<<"("<<path[i][0]<<","<<path[i][1]<<")"<<"->";
           cout<<"("<<path[bs][0]<<","<<path[bs][1]<<")"<<endl;
           cnt++;
       }
       return;
   }
   for(int i=1;i<=8;i++){
       int ax=dir[i][0]+x,ay=dir[i][1]+y;
       if(ax>=1&&ax<=8&&ay>=1&&ay<=8&&vis[ax][ay]==false&&map[ax][ay]==false){
           vis[ax][ay]=true;
           dfs(ax,ay,bs+1);
           vis[ax][ay]=false;
       }
   }
}
int main(){
   cin>>nx>>ny>>fx>>fy;
   for(int i=1;i<=8;i++)
       for(int j=1;j<=8;j++){
           cin>>map[i][j];
       }
   vis[nx][ny]=true;
   dfs(nx,ny,1);
   cout<<ans;
   return 0;
}

酷町豆刷题求解 C++ 0条评论 3 年，3 月前

Answer 1

已采纳

刘乐宸

新手天翼

dfs和dir这样写才对

int dir[9][2]={{0},{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
int sx, sy, ex, ey;
int mp[9][9], vis[9][9];
void dfs(int x, int y, int bs)
{
    path[bs][0]=x, path[bs][1]=y;
    if(x==ex && y==ey)
    {
        ans++;
        if(ans<=5)
        {
            for(int i=1; i<bs; i++)
            {
                cout<<'('<<path[i][0]<<','<<path[i][1]<<")->";
            }
            cout<<'('<<path[bs][0]<<','<<path[bs][1]<<")\n";
        }
        return ;
    } 
    for(int i=1; i<=8; i++)
    {
        int nx=x+dir[i][0], ny=y+dir[i][1];
        if(nx>=1&&nx<=8&&ny>=1&&ny<=8&&mp[nx][ny]==0&&!vis[nx][ny])
        {
            vis[nx][ny]=true;
            dfs(nx, ny, bs+1);
            vis[nx][ny]=false;
        }
    }
}

Answer 2

刘乐宸

新手天翼

#include <bits/stdc++.h>
using namespace std;
int ans, path[12000000][2];
int dir[9][2]={{0},{1,0},{-1,0},{0,-1},{0,1},{1,-1},{1,1},{-1,-1},{-1,1}};
int sx, sy, ex, ey;
int mp[9][9], vis[9][9];
void dfs(int x, int y, int bs)
{
    path[bs][0]=x, path[bs][1]=y;
    if(x==ex && y==ey)
    {
        ans++;
        if(ans<=5)
        {
            for(int i=1; i<bs; i++)
            {
                cout<<path[i][0]<<','<<path[i][1]<<"->";
            }
            cout<<path[bs][0]<<','<<path[bs][1]<<endl;
        }
        return ;
    } 
    for(int i=1; i<=8; i++)
    {
        int nx=x+dir[i][0], ny=y+dir[i][1];
        if(nx>=0&&nx<=8&&ny>=0&&ny<=8&&mp[nx][ny]==0&&!vis[nx][ny])
        {
            vis[nx][ny]=true;
            dfs(nx, ny, bs+1);
            vis[nx][ny]=false;
        }
    }
}
int main()
{
    cin >> sx >> sy >> ex >> ey;
    for(int i=1; i<=8; i++)
    {
        for(int j=1; j<=8; j++)
        {
            cin >> mp[i][j]; 
        }
    }
    if(mp[sx][sy]==1 || mp[ex][ey]==1)
    {
        cout<<1;
        return 0;
    }
    vis[sx][sy]=true;
    dfs(sx,sy,1);
    cout<<ans;
    return 0;
}

我这也不对……

问题标题: 酷町堂：5014

2 个回答: