#41994: 求解,不懂為甚麼用bfs會錯(queue),其他想法跟別人用迴圈 正確的程式碼是一樣的,用累加的


0402tim@gmail.com (owo)

學校 : 不指定學校
編號 : 134148
來源 : [140.117.248.203]
最後登入時間 :
2024-10-15 16:34:56
j122. 11957 - Checkers -- UVA | From: [140.117.248.201] | 發表日期 : 2024-09-16 21:28

#include <iostream>
#include<vector>
#include<queue>
#include<utility>
using namespace std;
vector<vector<char>> v;
vector<vector<int>> tr;
 
void bfs(int si,int sj,int n){
int ans=0;
 
queue<pair<int,int>> q;
q.push({si,sj});
tr[si][sj]=1;
while(!q.empty()){
pair<int,int> p=q.front();
q.pop();
 
int i=p.first,j=p.second;
 
if(i==0) return;
 
if(v[i-1][j+1]=='.'){
if(tr[i-1][j+1]==0)
q.push({i-1,j+1});
tr[i-1][j+1]+=tr[i][j];
}else if(i-2>0&&v[i-1][j+1]=='B'&&v[i-2][j+2]=='.'){
if(tr[i-2][j+2]==0)
q.push({i-2,j+2});
tr[i-2][j+2]+=tr[i][j];
}
if(v[i-1][j-1]=='.'){
if(tr[i-1][j-1]==0)
q.push({i-1,j-1});
tr[i-1][j-1]+=tr[i][j];
}else if(i-2>=0&&v[i-1][j-1]=='B'&&v[i-2][j-2]=='.'){
if(tr[i-2][j-2]==0)
q.push({i-2,j-2});
tr[i-2][j-2]+=tr[i][j];
}
 
}
for(int i=1;i<=n;i++) ans+=tr[1][i]%1000007;
cout<<ans<<endl;
}
 
int main(){
 
int t;
cin>>t;
for(int i=1;i<=t;i++){
int n,si,sj;
cin>>n;
v.assign(n+2,vector<char>(105,'0'));
tr.assign(n+2,vector<int>(105,0));
 
for(int i=1;i<n+1;i++){
for(int j=1;j<n+1;j++){
char c;
cin>>c; v[i][j]=c;
if(c=='W'){
si=i; sj=j;
}
}
}
 
cout<<"Case "<<i<<": ";
bfs(si,sj,n);
}
 
 
return 0;
}

 

 
ZeroJudge Forum