解题思路:
首先这是题DFS,题目给出了几个限制条件,就和普通的DFS没什么区别吧
注意事项:要记得判断箭数是否匹配
参考代码:
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define inf 1e9+7 #define ffr(i,a,b) for(int i=a;i<b;i++) #define mem(a,b) memset( a,b,sizeof a) #define Max(x,y) y>x?x=y:x=x int n; int up[30],le[30],vis[30][30],ans[900]; int dx[4]={0,1,0,-1}; int dy[4]={1,0,-1,0}; int a[30]={1},b[30]={1}; int orderr(int x,int y){ return y+n*x; } struct node{ int x,y,step; }; bool juge(){ for(int i=0;i<n;i++){ if(up[i]!=b[i] || le[i]!=a[i]) return false; } return true; } void dfs(int x,int y,int step){ if(x==n-1 && y== n-1&&juge()){ for(int i=0;i<step;i++){ cout<<ans[i]; if(i!=step-1) cout<<" "; } cout<<endl; return ; } for(int i=0;i<4;i++){ int cx=dx[i]+x,cy=dy[i]+y; if(cx>=0 &&cy>=0 &&cx<n &&cy<n && !vis[cx][cy] && a[cx]+1<=le[cx] && b[cy]+1<=up[cy]){ ans[step]=orderr(cx,cy); vis[cx][cy]=1; a[cx]++;b[cy]++; dfs(cx,cy,step+1); vis[cx][cy]=0; a[cx]--;b[cy]--; } } } int main() { std::ios::sync_with_stdio(false); cin>>n; for(int i=0;i<n;i++){ cin>>up[i]; } for(int i=0;i<n;i++){ cin>>le[i]; } vis[0][0]=1; cout<<0<<" "; dfs(0,0,0); return 0; }
0.0分
0 人评分
破解简单密码 (C语言代码)浏览:1768 |
简单的a+b (C语言代码)浏览:647 |
Biggest Number (C++代码)回溯法浏览:1614 |
C语言程序设计教程(第三版)课后习题6.4 (C语言代码)浏览:653 |
C语言程序设计教程(第三版)课后习题9.8 (Java代码)浏览:1642 |
C语言程序设计教程(第三版)课后习题11.3 (C语言代码)浏览:1039 |
淘淘的名单 (C语言代码)答案错误???浏览:595 |
WU-整数平均值 (C++代码)浏览:1245 |
剪刀石头布 (C语言代码)浏览:1436 |
C语言程序设计教程(第三版)课后习题11.3 (C语言代码)浏览:643 |