目录
八皇后
在国际象棋棋盘上放置八个皇后，要求每两个皇后之间不能直接吃掉对方
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int n=8, data[N][10], tt;
int a[10]; // a[y] = x (x,y) 有皇后
int b[10]; // b[y] = 1 (..,y) 有皇后
int c[20], d[20];// 对角线 (x+y), (x-y+n)
void dfs(int x){// dfs(x) : 当前第 x 行应该放皇后
if(x > n){ // 出口
++ tt;
// for(int i=1; i<=n; i++)data[tt][i] = a[i]; return;
// if(tt > 3) return;
cout<<"No."<<tt<<endl;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
cout<<(a[j]==i)<<" \n"[j==n];
}
for(int y=1; y<=n; y++)
if(!b[y] && !c[x+y] && !d[x-y+n]){
b[y]=c[x+y]=d[x-y+n]=1, a[x]=y;
dfs(x+1);
b[y]=c[x+y]=d[x-y+n]=0;
}
}
int main(){
dfs(1);
// int t,x; cin>>t;
// while(t--){
// cin>>x;
// for(int i=1; i<=n; i++) cout<<data[x][i]; cout<<endl;
// }
return 0;
}
八数码
在 3×3 的棋盘上，摆有八个棋子，每个棋子上标有 1 至 8 的某一数字。棋盘中留有一个空格，空格用 0 来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为 123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
string target = "123804765";
int d[][2] = {-1,0,1,0, 0,-1,0,1};
int bfs(string&s){
unordered_map<string,int> mp;
queue<string> q; q.push(s), mp[s]=1;
while(q.size()){
auto u = q.front(); q.pop();
if(u == target) return mp[u]-1;
int p = u.find('0');
for(int i=0; i<4; i++){
int x=p/3+d[i][0], y=p%3+d[i][1];
if(x<0 || x>=3 || y<0 || y>=3) continue;
string v=u;
swap(v[p], v[x*3 + y]);
if(!mp.count(v)) q.push(v), mp[v]=mp[u]+1;
}
}
return -1;
}
int main(){
string s;cin>>s;
cout<<bfs(s);
return 0;
}
红与黑
有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上，只能向上下左右四个方向的相邻的黑色瓷砖移动。
请写一个程序，计算你总共能够到达多少块黑色的瓷砖。
点击查看代码
#include<iostream>
#include<queue>
using namespace std;
const int N=22;
int n,m,ans,d[][2]={-1,0,1,0,0,-1,0,1};
bool st[N][N];
char s[N][N]; // string s[N];
void dfs(int x,int y){
ans ++, st[x][y] = 1;
for(int i=0; i<4; i++){
int a=x+d[i][0], b=y+d[i][1];
if(a<0||a>=n||b<0||b>=m) continue;
if(st[a][b] || s[a][b]!='.') continue;
dfs(a,b);
}
}
void bfs(int x,int y){
queue< pair<int,int> > q;
q.push({x,y}), st[x][y] = 1, ans++;
while(q.size()){
auto u = q.front(); q.pop(); x = u.first, y = u.second;
for(int i=0; i<4; i++){
int a=x+d[i][0], b=y+d[i][1];
if(a<0||a>=n||b<0||b>=m) continue;
if(st[a][b] || s[a][b]!='.') continue;
q.push({a,b}), st[a][b] = 1, ans ++;
}
}
}
int main(){
cin>>m>>n;
for(int i=0; i<n; i++) cin>>s[i];
for(int i=0; i<n; i++)
for(int j=0; j<m; j++) if(s[i][j]=='@') bfs(i,j);
cout<<ans;
return 0;
}