1 月 26日算法练习

九宫幻方

小明最近在教邻居家的小朋友小学奥数，而最近正好讲述到了三阶幻方这个部分，三阶幻方指的是将1~9不重复的填入一个33的矩阵当中，使得每一行、每一列和每一条对角线的和都是相同的。
三阶幻方又被称作九宫格，在小学奥数里有一句非常有名的口诀：“二四为肩，六八为足，左三右七，戴九履一，五居其中”，通过这样的一句口诀就能够非常完美的构造出一个九宫格来。
4 9 2
3 5 7
8 1 6
有意思的是，所有的三阶幻方，都可以通过这样一个九宫格进行若干镜像和旋转操作之后得到。现在小明准备将一个三阶幻方（不一定是上图中的那个）中的一些数抹掉，交给邻居家的小朋友来进行还原，并且希望她能够判断出究竟是不是只有一个解。
而你呢，也被小明交付了同样的任务，但是不同的是，你需要写一个程序~
【输入格式】
输入仅包含单组测试数据。
每组测试数据为一个33的矩阵，其中为0的部分表示被小明抹去的部分。
对于100%的数据，满足给出的矩阵至少能还原出一组可行的三阶幻方。

【输出格式】
如果仅能还原出一组可行的三阶幻方，则将其输出，否则输出“Too Many”（不包含引号）。

【样例输入】

0 7 2
0 5 0
0 3 0
【样例输出】

6 7 2
1 5 9
8 3 4

思路：dfs，回溯

#include<iostream>
#include<utility>using namespace std;int a[5][5],ans[5][5];
pair<int, int> p[10];
int n,cnt;
int vis[10];int check(){int sum = a[1][1]+a[2][2]+a[3][3];if(sum!=a[1][3]+a[2][2]+a[3][1])return 0;for(int i=1;i<=3;i++){int tmp1=0,tmp2=0;for(int j=1;j<=3;j++){tmp1+=a[i][j],tmp2+=a[j][i];}if(sum!=tmp1||sum!=tmp2)return 0;}return 1;
}void dfs(int now){if(now > n){if(check()){cnt++;for(int i=1;i<=3;i++){for(int j=1;j<=3;j++){ans[i][j] = a[i][j];}}}return;}int x = p[now].first,y = p[now].second;for(int k=1;k<=9;k++){if(vis[k])continue;a[x][y] = k;vis[k] = 1;dfs(now + 1);a[x][y]=0;vis[k]=0;}}int main( ){for(int i=1;i<=3;i++){for(int j=1;j<=3;j++){cin>>a[i][j];if(!a[i][j])p[++n] = make_pair(i, j);vis[a[i][j]] = 1;}}dfs(1);if(cnt==1){for(int i=1;i<=3;i++){for(int j=1;j<=3;j++){cout<<ans[i][j]<<" \n"[j==3];}}}else cout<<"Too Many\n";return 0;
}

穿越雷区

X 星的坦克战车很奇怪，它必须交替地穿越正能量辐射区和负能量辐射区才能保持正常运转，否则将报废。
某坦克需要从 A 区到 B 区去（A，B 区本身是安全区，没有正能量或负能量特征），怎样走才能路径最短？
已知的地图是一个方阵，上面用字母标出了 A，B 区，其它区都标了正号或负号分别表示正负能量辐射区。
例如：

A + - + -
- + - - +
- + + + -
+ - + - +
B + - + -

坦克车只能在水平或垂直方向上移动到相邻的区。
输入格式

输入第一行是一个整数n，表示方阵的大小， 4 ≤ n < 100。
接下来是n 行，每行有n 个数据，可能是 A，B，+，- 中的某一个，中间用空格分开。
A，B 都只出现一次。
输出格式

要求输出一个整数，表示坦克从A区到B区的最少移动步数。如果没有方案，则输出-1
样例输入

5
A + - + -
- + - - +
- + + + -
+ - + - +
B + - + -

样例输入
10
dfs，剪枝

#include<iostream>
#include<utility>
using namespace std;
const int N = 1e3 + 5;
int n,ans;
pair<int,int> st,ed;
int a[N][N],vis[N][N];void dfs(int x,int y,int cnt){if(cnt>ans)return;if(cnt>vis[x][y])return;if(x>n||x<1||y<1||y>n)return;if(x==ed.first&&y==ed.second){ans=cnt;return;}vis[x][y]=cnt;int nx = x-1,ny=y;if(a[nx][y]!=a[x][y])dfs(nx,ny,cnt+1);nx = x+1,ny=y;if(a[nx][y]!=a[x][y])dfs(nx,ny,cnt+1);nx = x,ny = y-1;if(a[x][ny]!=a[x][y])dfs(nx,ny,cnt+1);nx = x,ny = y+1;if(a[x][ny]!=a[x][y])dfs(nx,ny,cnt+1);
}int main(){char x;cin>>n;ans = 0x3f3f3f3f;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)vis[i][j]=0x3f3f3f3f;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin>>x;if(x=='A')st.first=i,st.second=j,a[i][j]=-1;else if(x=='B')ed.first=i,ed.second=j,a[i][j]=-1;else if(x=='+')a[i][j]=1;else a[i][j]=0;}}dfs(st.first,st.second,0);cout<<ans<<'\n';return 0;
}

走迷宫

给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。

最初，有一个人位于左上角 (1,1) 处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。

请问，该人从左上角移动至右下角 (n,m) 处，至少需要移动多少次。

数据保证 (1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路。

输入格式

第一行包含两个整数 n 和 m。

接下来 n 行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。

输出格式

输出一个整数，表示从左上角移动至右下角的最少移动次数。

数据范围

1≤n,m≤100

输入样例：

5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
输出样例：

8

• bfs

#include<iostream>
#include<queue>
#include<utility>
#include<cstring>
using namespace std;
using PII = pair<int,int>;
const int N = 1e2+5;
int w,h;
int mp[N][N],ans[N][N];
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
void bfs(){queue<pair<int,int>> q;q.push({0,0});memset(ans,-1,sizeof(ans));ans[0][0] = 0;while(!q.empty()){PII front = q.front();q.pop();for(int k=0;k<4;k++){int nx=dx[k]+front.first,ny=dy[k]+front.second;if(nx>=0&&nx<w&&ny>=0&&ny<h&&ans[nx][ny]==-1&&mp[nx][ny]==0){ans[nx][ny]=ans[front.first][front.second]+1;q.push({nx,ny});}}}
}int  main( ){cin>>w>>h;for(int i=0;i<w;i++)for(int j=0;j<h;j++)cin>>mp[i][j];bfs();cout<<ans[w-1][h-1]<<'\n';return 0;
}