請網(wǎng)站制作公司費用培訓機構(gòu)不退費最有效方式
文章目錄
- 九宮幻方
- 穿越雷區(qū)
- 走迷宮
九宮幻方
小明最近在教鄰居家的小朋友小學奧數(shù),而最近正好講述到了三階幻方這個部分,三階幻方指的是將1~9不重復的填入一個33的矩陣當中,使得每一行、每一列和每一條對角線的和都是相同的。
三階幻方又被稱作九宮格,在小學奧數(shù)里有一句非常有名的口訣:“二四為肩,六八為足,左三右七,戴九履一,五居其中”,通過這樣的一句口訣就能夠非常完美的構(gòu)造出一個九宮格來。
4 9 2
3 5 7
8 1 6
有意思的是,所有的三階幻方,都可以通過這樣一個九宮格進行若干鏡像和旋轉(zhuǎn)操作之后得到。現(xiàn)在小明準備將一個三階幻方(不一定是上圖中的那個)中的一些數(shù)抹掉,交給鄰居家的小朋友來進行還原,并且希望她能夠判斷出究竟是不是只有一個解。
而你呢,也被小明交付了同樣的任務,但是不同的是,你需要寫一個程序~
【輸入格式】
輸入僅包含單組測試數(shù)據(jù)。
每組測試數(shù)據(jù)為一個33的矩陣,其中為0的部分表示被小明抹去的部分。
對于100%的數(shù)據(jù),滿足給出的矩陣至少能還原出一組可行的三階幻方。
【輸出格式】
如果僅能還原出一組可行的三階幻方,則將其輸出,否則輸出“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;
}
穿越雷區(qū)
X 星的坦克戰(zhàn)車很奇怪,它必須交替地穿越正能量輻射區(qū)和負能量輻射區(qū)才能保持正常運轉(zhuǎn),否則將報廢。
某坦克需要從 A 區(qū)到 B 區(qū)去(A,B 區(qū)本身是安全區(qū),沒有正能量或負能量特征),怎樣走才能路徑最短?
已知的地圖是一個方陣,上面用字母標出了 A,B 區(qū),其它區(qū)都標了正號或負號分別表示正負能量輻射區(qū)。
例如:
A + - + -
- + - - +
- + + + -
+ - + - +
B + - + -
坦克車只能在水平或垂直方向上移動到相鄰的區(qū)。
輸入格式
輸入第一行是一個整數(shù)n,表示方陣的大小, 4 ≤ n < 100。
接下來是n 行,每行有n 個數(shù)據(jù),可能是 A,B,+,- 中的某一個,中間用空格分開。
A,B 都只出現(xiàn)一次。
輸出格式
要求輸出一個整數(shù),表示坦克從A區(qū)到B區(qū)的最少移動步數(shù)。如果沒有方案,則輸出-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 的二維整數(shù)數(shù)組,用來表示一個迷宮,數(shù)組中只包含 0 或 1,其中 0 表示可以走的路,1 表示不可通過的墻壁。
最初,有一個人位于左上角 (1,1) 處,已知該人每次可以向上、下、左、右任意一個方向移動一個位置。
請問,該人從左上角移動至右下角 (n,m) 處,至少需要移動多少次。
數(shù)據(jù)保證 (1,1) 處和 (n,m) 處的數(shù)字為 0,且一定至少存在一條通路。
輸入格式
第一行包含兩個整數(shù) n 和 m。
接下來 n 行,每行包含 m 個整數(shù)(0 或 1),表示完整的二維數(shù)組迷宮。
輸出格式
輸出一個整數(shù),表示從左上角移動至右下角的最少移動次數(shù)。
數(shù)據(jù)范圍
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;
}