前提・実現したいこと
こちらAtCoderの問題(深さ優先探索問題)
https://atcoder.jp/contests/arc031/tasks/arc031_2
でACのコードに一部コードを追加すると、1つだけWAとなり、その追加したコードによる誤りを教えていただきたい。
追加した理由は前後左右に1つも陸がなければ、探索する必要がなくなると考えたからです。
該当のソースコード
c++
1 2#include "bits/stdc++.h" 3 4using namespace std; 5typedef long long ll; 6#define rep(i, j, n) for (int i = j; i < n; i++) 7#define out(ans) cout << ans << endl; 8const long long mod = 1e9 + 7; 9 10int h=10,w=10; 11int a[4]={-1,0,1,0},b[4]={0,-1,0,1}; 12string s[11],c[11]; 13 14void dfs(int x,int y){ 15 rep(i,0,4){ 16 int tx=x+a[i],ty=y+b[i]; 17 if(tx>=0&&ty>=0&&tx<w&&ty<h&&c[ty][tx]=='o'){ 18 c[ty][tx]='x'; 19 dfs(tx,ty); 20 } 21 } 22} 23 24int main(){ 25 26 rep(i,0,h) cin>>s[i]; 27 28 rep(i,0,h)rep(j,0,w){ 29 if(s[i][j]=='o')continue; 30//--------------------------ここから 31 int num=0; 32 rep(i,0,4){ 33 if(j+a[i]>=0&&i+b[i]>=0&&j+a[i]<10&&i+b[i]<10&&s[i+b[i]][j+a[i]]=='o')num++; 34 } 35 if(num==0)continue; 36//---------------------------ここまでを追加 37 rep(k,0,h) c[k]=s[k]; 38 c[i][j]='o'; 39 int cnt=0; 40 rep(k,0,h)rep(l,0,w){ 41 if(c[k][l]=='o') { 42 c[k][l]='x'; 43 dfs(l,k); 44 cnt++; 45 } 46 } 47 if(cnt==1){ 48 out("YES"); 49 return 0; 50 } 51 } 52 53 out("NO") 54 55 return 0; 56} 57
回答1件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2019/08/13 04:09