Liny_@NotePad

沉迷ACG中

Don't Get Rooked

YOYO posted @ 2008年11月24日 06:24 in 【ICPC】解题报告 with tags 回溯 , 1880 阅读

PKU 1315：http://acm.pku.edu.cn/JudgeOnline/problem?id=1315

 由于n<=4，直接暴力回溯即可 = =。

  1. #include<iostream>
  2. using namespace std;
  3. int n,m;
  4. int map[10][10];
  5.  
  6. bool check(int x, int y){
  7.         int i;
  8.         for(i=x-1;i>=0&&map[i][y]>=0;i--){
  9.                 if(map[i][y]==1)return false;
  10.         }
  11.         for(i=x+1;i<n&&map[i][y]>=0;i++){
  12.                 if(map[i][y]==1)return false;
  13.         }
  14.         for(i=y-1;i>=0&&map[x][i]>=0;i--){
  15.                 if(map[x][i]==1)return false;
  16.         }
  17.         for(i=y+1;i<n&&map[x][i]>=0;i++){
  18.                 if(map[x][i]==1)return false;
  19.         }
  20.         return true;
  21. }
  22.  
  23. void search(int x, int y, int t){
  24.         map[x][y]=1;
  25.         int i,j;
  26.         for(i=y+1;i<n;i++){
  27.                 if(map[x][i]==-1)continue;
  28.                 if(check(x,i)){
  29.                         search(x,i,t+1);
  30.                 }
  31.         }
  32.         for(i=x+1;i<n;i++){
  33.                 for(j=0;j<n;j++){
  34.                         if(map[i][j]==-1)continue;
  35.                         if(check(i,j)){
  36.                                 search(i,j,t+1);
  37.                         }
  38.                 }
  39.         }
  40.         if(t>m)m=t;
  41.         map[x][y]=0;
  42. }
  43.  
  44. int main(){
  45.         while(cin>>n&&n){
  46.                 m = 0;
  47.                 int i,j;
  48.                 for(i=0;i<n;i++){
  49.                         for(j=0;j<n;j++){
  50.                                 char c;cin>>c;
  51.                                 if(c=='X'){
  52.                                         map[i][j]=-1;
  53.                                 }else{
  54.                                         map[i][j]=0;
  55.                                 }
  56.                         }
  57.                 }
  58.                 for(i=0;i<n;i++){
  59.                         for(j=0;j<n;j++){
  60.                                 if(map[i][j]==-1)continue;
  61.                                 search(i,j,1);
  62.                                 map[i][j]=0;
  63.                         }
  64.                 }
  65.                 cout<<m<<endl;
  66.         }
  67.         return 0;
  68. }

狂复习简单题……

  • 无匹配
Small_feed 评论 (0)

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter