ABC 015 C - 高橋くんのバグ探し
問題概要
省略
解法
nやkは小さいので、全探索できるな。でも、kが毎回変わるから、単純にループを書こうと思うと、kに応じて、ループの回数を変えたコードを書かなければならなくなり、めんどくさいので、dfsで何回ループをしなければならないかを引数に持たせやればいい。
ミス
なし。
コード
#include <iostream> #include <cstdio> using namespace std; #define rep(i,n) for(int i=0;i<(n);i++) int t[10][10]; int n, k; bool flag = false; void dfs(int x, int num){ if(num == n){ if(x == 0) flag = true; return; } rep(i, k){ dfs(x ^ t[num][i], num + 1); } } int main(void){ cin >> n >> k; rep(i, n)rep(j, k) cin >> t[i][j]; dfs(0, 0); if(flag) printf("Found\n"); else printf("Nothing\n"); return 0; }
下のように返り値でflag返すような書き方は得意じゃない。
#include <iostream> #include <cstdio> using namespace std; #define rep(i,n) for(int i=0;i<(n);i++) int t[10][10]; int n, k; bool dfs(int x, int num){ if(num == n){ if(x == 0) return true; else return false; } rep(i, k){ if(dfs(x ^ t[num][i], num + 1)) return true;; } return false; } int main(void){ cin >> n >> k; rep(i, n)rep(j, k) cin >> t[i][j]; if(dfs(0, 0)) printf("Found\n"); else printf("Nothing\n"); return 0; }