高级天翼
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
//CODE
//#pragma GCC optimize(3)
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
using namespace std;
int dir[8][2] = {{-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {-1, 0}, {1, -1}, {0, -1}, {-1, -1}};
int cnt;
bool G[10][10];
bool vis[10][10];
int sx, sy, ex, ey;
int a[100000], b[100000];
void dfs(int x, int y, int t) {
a[t] = x, b[t] = y;
if (x == ex && y == ey) {
cnt ++;
if (cnt <= 5) {
for (int i = 1; i < t; i ++) {
cout << "(" <<a[i] << "," << b[i] << ")" << "->";
}
cout << "(" << ex << "," << ey << ")" << endl;
}
return ;
}
for (int i = 0; i < 8; i ++) {
int nx = x + dir[i][0], ny = y + dir[i][1];
if (nx >= 1 && nx <= 8 && ny >= 1 && ny <= 8 && !vis[nx][ny] && !G[nx][ny]) {
vis[nx][ny] = true;
dfs(nx, ny, t + 1);
vis[nx][ny] = false;
}
}
}
int main() {
// freopen ("题目名.in", "r", stdin);
// freopen ("题目名.out", "w", stdout);
cin >> sx >> sy >> ex >> ey;
for (int i = 1; i <= 8; i ++) {
for (int j = 1; j <= 8; j ++) {
cin >> G[i][j];
}
}
vis[sx][sy] = true;
dfs(sx, sy, 1);
vis[sx][sy] = false;
cout << cnt;
// fclose (stdin);
// fclose (stdout);
return 0;//好习惯！
}
20分
张恩泽在2021-07-05 15:21:34追加了内容
顶!!
张恩泽在2021-07-07 15:26:25追加了内容
悬赏完再町！！！!
