pass_river
Mathematical Modeling Homework #### Question
Result
#### SC
#include<bits/stdc++.h>
using namespace std;
int m[12][12][12];
char s[10000];
int p=0;
/*
-3 0 1
-2 -1 2
-1 -2 3
0 -3 4
+3 0 5
+2 +1 6
+1 +2 7
0 +3 8
-2 0 a
-1 -1 b
0 -2 c
+2 0 d
+1 +1 e
0 +2 f
-1 0 g
0 -1 h
+1 0 i
0 +1 j
用字符串编码来记录每一步
如果步不对 则删掉
flag=1 是下一步左下 -1是下一步右上
*/
void print(){
//cout<<"q";
for(int i=1;i<=100;i++){
if(s[i]=='0') continue;
cout<<s[i]<<" ";
}
cout<<endl;
exit(0);
}
void find(int x, int y, int flag){
/// cout<<"a"<<endl;
if(x==0&&y==0)
print();
if(flag==1){
// cout<<"!";
if(m[x-3][y][flag-1]==1){
p=p+1;
s[p]='1';
m[x-3][y][flag-1]=2;// 2 refers to can&had 标记
find(x-3,y,flag-1);
s[p]='0';
p=p-1;
//cout<<"1";
}
if(m[x-2][y-1][flag-1]==1){
p=p+1;
s[p]='2';
m[x-2][y-1][flag-1]=2;// 2 refers to can&had 标记
find(x-2,y-1,flag-1);
s[p]='0';
//cout<<"2";
}
if(m[x-1][y-2][flag-1]==1){
p=p+1;
s[p]='3';
m[x-1][y-2][flag-1]=2;// 2 refers to can&had 标记
find(x-1,y-2,flag-1);
s[p]='0';
p=p-1;
//cout<<"1";
}
if(m[x][y-3][flag-1]==1){
p=p+1;
s[p]='4';
m[x][y-3][flag-1]=2;// 2 refers to can&had 标记
find(x,y-3,flag-1);
s[p]='0';
p=p-1;
//cout<<"1";
}
if(m[x-2][y][flag-1]==1){
p=p+1;
s[p]='a';
m[x-2][y][flag-1]=2;// 2 refers to can&had 标记
find(x-2,y,flag-1);
s[p]='0';
p=p-1;
//cout<<"1";
}
if(m[x-1][y-1][flag-1]==1){
p=p+1;
s[p]='b';
m[x-1][y-1][flag-1]=2;// 2 refers to can&had 标记
find(x-1,y-1,flag-1);
s[p]='0';
p=p-1;
//cout<<"1";
}
if(m[x][y-2][flag-1]==1){
p=p+1;
s[p]='c';
m[x][y-2][flag-1]=2;// 2 refers to can&had 标记
find(x,y-2,flag-1);
s[p]='0';
p=p-1;
//cout<<"1";
}
if(m[x-1][y][flag-1]==1){
p=p+1;
s[p]='g';
m[x-1][y][flag-1]=2;// 2 refers to can&had 标记
find(x-1,y,flag-1);
s[p]='0';
p=p-1;
//cout<<"1";
}
if(m[x][y-1][flag-1]==1){
p=p+1;
s[p]='h';
m[x][y-1][flag-1]=2;// 2 refers to can&had 标记
find(x,y-1,flag-1);
s[p]='0';
p=p-1;
//cout<<"1";
}
}
if(flag==0){
//cout<<"o";
if(m[x+3][y][flag+1]==1){
p=p+1;
s[p]='5';
m[x+3][y][flag+1]=2;// 2 refers to can&had 标记
find(x+3,y,flag+1);
s[p]='0';
p=p-1;
}
if(m[x+2][y+1][flag+1]==1){
p=p+1;
s[p]='6';
m[x+2][y+1][flag+1]=2;// 2 refers to can&had 标记
find(x+2,y+1,flag+1);
s[p]='0';
p=p-1;
}
if(m[x+1][y+2][flag+1]==1){
p=p+1;
s[p]='7';
m[x+1][y+2][flag+1]=2;// 2 refers to can&had 标记
find(x+1,y+2,flag+1);
s[p]='0';
p=p-1;
}
if(m[x][y+3][flag+1]==1){
p=p+1;
s[p]='8';
m[x][y+3][flag+1]=2;// 2 refers to can&had 标记
find(x,y+3,flag+1);
s[p]='0';
p=p-1;
}
if(m[x+2][y][flag+1]==1){
p=p+1;
s[p]='d';
m[x+2][y][flag+1]=2;// 2 refers to can&had 标记
find(x+2,y,flag+1);
s[p]='0';
p=p-1;
//cout<<"1";
}
if(m[x+1][y+1][flag+1]==1){
p=p+1;
s[p]='e';
m[x+1][y+1][flag+1]=2;// 2 refers to can&had 标记
find(x+1,y+1,flag+1);
s[p]='0';
p=p-1;
//cout<<"1";
}
if(m[x][y+2][flag+1]==1){
p=p+1;
s[p]='f';
m[x][y+2][flag+1]=2;// 2 refers to can&had 标记
find(x,y+2,flag+1);
s[p]='0';
p=p-1;
//cout<<"1";
}
if(m[x+1][y][flag+1]==1){
p=p+1;
s[p]='i';
m[x+1][y][flag+1]=2;// 2 refers to can&had 标记
find(x+1,y,flag+1);
s[p]='0';
p=p-1;
//cout<<"1";
}
if(m[x][y+1][flag+1]==1){
p=p+1;
s[p]='j';
m[x][y+1][flag+1]=2;// 2 refers to can&had 标记
find(x,y+1,flag+1);
s[p]='0';
p=p-1;
//cout<<"1";
}
}
}
int main(){
for(int i=1;i<=10000;i++)
s[i]='0';
for(int i=1;i<=10;i++)
for(int j=1;j<=10;j++)
for(int k=1;k<=10;k++)
m[i][j][k]=0;
for(int i=0;i<=4;i++){
m[0][i][1]=1;//[1] down&left 1:can&haven't
m[0][i][0]=1;//[0] up&right
m[i][i][1]=1;
m[i][i][0]=1;
m[4][i][1]=1;
m[4][i][0]=1;
}
m[4][4][1]=0;
m[4][4][0]=0;
// for(int i=0;i<=5;i++){
// for(int j=0;j<=5;j++){
// cout<<m[i][j][0]<<" ";
// }
// cout<<endl;
// }
// for(int i=0;i<=5;i++){
// for(int j=0;j<=5;j++){
// cout<<m[i][j][1]<<" ";
// }
// cout<<endl;
// }
find(4,4,1);
return 0;
}