ZOJ-Crashing Balloon

先從最大的數開始, 深度優先遍歷.?

如果是 m 和 n 的公因子, 先遍歷m的, 回溯返回的數值還是公因子, 再遍歷n.

如果有某一或幾條路徑可以讓 m 和 n 變成 1 ,說明 m 和 n 不沖突, m 勝利.

如果沒有找到一條路徑當 n 分解完成時, m 也分解完成, 則判定 m說謊(無論 n 是否說謊), n 勝利.

 1 #include <iostream>
 2 using namespace std;
 3 bool flagM, flagN;
 4 void dfs(int m, int n, int factor){
 5     //cout << "M N:" << m <<" "<< n << endl;
 6     if (m == 1 && n == 1){//兩個都被完全因式分解
 7         //cout << flagM << flagN << endl;
 8         flagM = flagN = true;
 9         return;
10     }
11     if (n == 1)//小數被分解完，大數還未被分解完 
12         flagN = true;
13     while (factor>1){
14         
15         if (m%factor == 0) {
16             //cout <<"FLAG:" << flagM << flagN << endl;
17             dfs(m / factor, n, factor - 1);
18         }
19         
20         if (n%factor == 0) {
21             cout << flagM << flagN << endl;
22             dfs(m, n / factor, factor - 1);
23         }
24         factor--;
25         //cout << "FACTOR:" <<factor << endl;
26     }
27 }
28 int main(){
29     int m, n;
30     while (cin>>m>>n){
31         if (m<n){
32             int t = m;
33             m = n;
34             n = t;
35         }
36         flagM = flagN = false;
37         dfs(m, n, 100);
38         if (!flagM && flagN)
39             cout << n << endl;
40         else
41             cout << m << endl;
42     }
43     return 0;
44 }

轉載于:https://www.cnblogs.com/miyamochio/p/9675866.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/388475.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/388475.shtml
英文地址，請注明出處：http://en.pswp.cn/news/388475.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！