c780 - 106北二5.炮打眾卒遊戲
題目描述
題目描述一個 n × m 的棋盤，棋盤上所有位置都有卒，炮從左上角開始，可以沿著水平或垂直方向射擊卒。炮射擊的規則是，如果炮與卒之間只有一個卒，則可以射擊該卒。題目要求計算炮最多可以射擊多少個卒。
解題思路
這題使用遞迴回溯法來模擬炮的射擊過程。func 函數模擬炮從給定的位置 (x, y) 出發，射擊卒的過程。它嘗試沿著四個方向（上、下、左、右）尋找可以射擊的卒。如果找到可以射擊的卒，則將該卒射擊掉（設為 0），然後遞迴呼叫 func 函數，繼續射擊。射擊完後，將該卒恢復（設為 1），以便回溯到之前的狀態。maxi 變數用於記錄炮最多可以射擊的卒的數量。
複雜度分析
- 時間複雜度: O(4^(n*m))，在最壞情況下，炮可能需要嘗試所有可能的射擊路徑。
- 空間複雜度: O(n*m)，主要用於儲存棋盤的狀態和遞迴呼叫堆疊。
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <iostream>
using namespace std;
int n, m, maxi, a[9][9];
inline void func(int x, int y, int steps){
int count = 0;
bool flag = 0;
if(x<n-1)
for (int i = x+1; i < n; ++i){
if (a[i][y]) ++count;
if (count == 2){
a[i][y] = 0;
func(i, y, steps+1);
a[i][y] = 1;
flag = 1;
break;
}
}
count = 0;
if(x>0)
for (int i = x-1; i >= 0; --i){
if (a[i][y]) ++count;
if (count == 2){
a[i][y] = 0;
func(i, y, steps+1);
a[i][y] = 1;
flag = 1;
break;
}
}
count = 0;
if(y<m-1)
for (int i = y+1; i < m; ++i){
if (a[x][i]) ++count;
if (count == 2){
a[x][i] = 0;
func(x, i, steps+1);
a[x][i] = 1;
flag = 1;
break;
}
}
count = 0;
if(y>0)
for (int i = y-1; i >= 0; --i){
if (a[x][i]) ++count;
if (count == 2){
a[x][i] = 0;
func(x, i, steps+1);
a[x][i] = 1;
flag = 1;
break;
}
}
if (!flag && steps > maxi) maxi = steps;
}
int main(){
cin >> n >> m;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
a[i][j] = 1;
a[0][0] = 0;
func(0, 0, 0);
cout << maxi ;
}