Отримання знань

дистанційна підтримка освіти школярів


Иллюзорное преследование
http://acm.pku.edu.cn/JudgeOnline/problem?id=1071

   Входные данные

   Выходные данные

   Пример входных данных

   Пример выходных данных

   Анализ условия и обсуждение идеи решения

   Пример решения на C++:

#include "iostream" 
using namespace std;
int b[1000][3],k,ge,m,n;
bool a[102][102],pp;
void dfs(int x,int y,int k0){
int i,p,q,f;
p=b[k0][0];q=b[k0][1];f=b[k0][2];
if(pp==1) return ;
if(k0==k) {ge++;pp=1;return ;}
if(p==q){
if(f==1 && y+q <= n){
for(i=0; i <= q; i++)
if(a[x][y+i]==1) break;
if(i==q+1) dfs(x,y+q,k0+1);}
if(f==2 && y-q >= 1){
for(i=0; i <= q; i++)
if(a[x][y-i]==1) break;
if(i==q+1) dfs(x,y-q,k0+1);}
if(f==3 && x-q >= 1){
for(i=0; i <= q; i++)
if(a[x-i][y]==1) break;
if(i==q+1) dfs(x-q,y,k0+1);}
if(f==4 && x+q <= m){
for(i=0; i <= q; i++)
if(a[x+i][y]==1) break;
if(i==q+1) dfs(x+q,y,k0+1);}
}
else {
if(f==1 && y+q <= n){
for(i=0; i <= q; i++)
if(a[x][y+i]==1) break;
if(i==q+1) dfs(x,y+q,k0+1);}
if(f==2 && y-q >= 1){
for(i=0; i <= q; i++)
if(a[x][y-i]==1) break;
if(i==q+1) dfs(x,y-q,k0+1);}
if(f==3 && x-q >= 1){
for(i=0; i <= q; i++)
if(a[x-i][y]==1) break;
if(i==q+1) dfs(x-q,y,k0+1);}
if(f==4 && x+q <= m){
for(i=0;i <= q; i++)
if(a[x+i][y]==1) break;
if(i==q+1) dfs(x+q,y,k0+1);}
if(f==1 && y+p <= n){
for(i=0; i <= p; i++)
if(a[x][y+i]==1) break;
if(i==p+1) dfs(x,y+p,k0+1);}
if(f==2 && y-p >= 1){
for(i=0; i <= p; i++)
if(a[x][y-i]==1) break;
if(i==p+1) dfs(x,y-p,k0+1);}
if(f==3 && x-p >= 1){
for(i=0; i <= p; i++)
if(a[x-i][y]==1) break;
if(i==p+1) dfs(x-p,y,k0+1);}
if(f==4 && x+p <= m){
for(i=0; i <= p; i++)
if(a[x+i][y]==1) break;
if(i==p+1) dfs(x+p,y,k0+1);}
}
}
int main(){
int i,j,t,sum;
char c;
cin >> t;
while(t && t--){
cin >> m >> n;
for(i=0; i<= 101; i++)
for(j=0; j <= 101; j++) a[i][j]=1;
for(i=1; i <=m; i++)
for(j=1; j <=n; j++) cin >> a[i][j];
k=0;
while(cin >> b[k][0] >> b[k][1]){
if(b[k][0]==0 && b[k][1]==0) break;
cin >> c;
if(c=='R') b[k][2]=1;
else if(c=='L') b[k][2]=2;
else if(c=='U') b[k][2]=3;
else if(c=='D') b[k][2]=4;
k++;}
sum=0;
for(i=1; i <= m; i++)
for(j=1; j <= n; j++){
if(a[i][j]==0){
ge=0;pp=0;
dfs(i,j,0);
sum+=ge;}
}
cout << sum << endl;}
return 0;
}

 

Попередня Зміст Наступна
В системі: гості - (1); користувачі - (0)