6、数字接龙
题目 数字接龙
思路分析
就是这题陷进去了 浪费了一个多小时
一开始说这道题有问题 然后我先写了第七题 回过头来才看的这题 早知道也看一眼最后一题了
我一直找不到bug在哪里 导致答案一直输出-1 ……
然后就不服气了 因为思路都没什么问题 一想到自己写半天和别人直接输出-1是一样的分就气 然后一直改 导致最后一题看都没看 因为不确定最后一题能写出来 万一写不出 这题呼之欲出了又没拿到 就亏大了
结果就是 在两题选一题拿分的情况下 选择了两题都不拿分hh
回到寝室一眼就看出来了问题……
所以懊悔不已 要是出去上个厕所 转变一下思路 说不定两题都能写出来 70分省一前几名都有了 可惜可惜
代码实现
/*
左上角00出发 到n-1,n-1 但不是线性dp的模型
可以往8个方向走 可以借鉴经验 一定不会往上和左上 和左走
意味着 可以往 右上 右 右下 下 左下 5个方向走
还得有个要求 走过的路 上面的数要是012…k-1的循环
每个格子只能走一次 且不能交叉路径
后面两个限制貌似可以用前面的分析抵消
要求找到路径 和 回溯
应该是bfs dfs 数据范围也正常 10 没跑了
整理一下 从起点 0，0 走到 终点n-1,n-1
每个点可以往5个方向拓展 右上 右 右下 下 左下
要求字典序最小 那就是这个拓展顺序 无需改变
拓展的时候 要另外加一个判断 要是上一个数+1 若上一个数为k-1 则该数为0 可能要传入一个last变量
*/
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef pair<int,int> PII;
const int N=15;
int n,k;
int g[N][N];
bool st[N][N];
int path[N];
bool success=false;
int dx[5]={-1,0,1,1,1};
int dy[5]={1,1,1,0,-1};
int p[5]={1,2,3,4,5};
bool isVaild(int x,int y){
return x>=0 && x<=n-1 && y>=0 && y<=n-1 && !st[x][y];
}
//void print_path(int x,int y){
// if(x==0 && y==0)
// return;
// if(pre[x][y]==1)//这个点由上个点往右上走来 往左下找回上个点
// print_path(x+1,y-1);
// if(pre[x][y]==2)
// print_path(x,y-1);
// if(pre[x][y]==3)
// print_path(x-1,y-1);
// if(pre[x][y]==4)
// print_path(x-1,y);
// if(pre[x][y]==5)
// print_path(x-1,y+1);
// cout<<pre[x][y];
//}
bool check(int ux,int uy,int nx,int ny){
if(g[ux][uy]==k-1){
if(g[nx][ny]==0)
return true;
}
else{
if(g[nx][ny]==g[ux][uy]+1)
return true;
}
return false;
}
void dfs(int x,int y,int u){
if(u==n*n-1){
for(int i=0;i<n*n-1;i++){
cout<<path[i];
}
success=true;
return;
}
for(int i=0;i<5;i++){
int nx=x+dx[i],ny=y+dy[i];
if(isVaild(nx,ny) && check(x,y,nx,ny)){
st[nx][ny]=true;
path[u]=p[i];
dfs(nx,ny,u+1);
st[nx][ny]=false;
path[u]=-1;
}
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>k;
//题目说读n行 又给了空格 鬼知道是不是g[i][j]一个一个读入 万一只读3次就寄了
//按行处理 防恶心
string s;
getline(cin,s);
for(int i=0;i<n;i++){
getline(cin,s);
for(int k=0,j=0;k<s.size();k++){
if(s[k]!=' ')
g[i][j++]=s[k]-'0';
}
}
// for(int i=0;i<n;i++){
// for(int j=0;j<n;j++){
// cout<<g[i][j]<<" ";
// }
// cout<<endl;
// }
dfs(0,0,0);
if(!success)
cout<<"-1";
return 0;
}
💬 评论