Snowdream

I'm awake but my world is half asleep
posts - 403, comments - 310, trackbacks - 0, articles - 7
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

USACO 1.1.4 The Clocks

Posted on 2007-05-30 21:34 ZelluX 阅读(672) 评论(0)  编辑  收藏 所属分类: Algorithm

本来想练习了下deque的使用。用BFS,每个结点都记录了到目前为止转动的情况。结果发现内存消耗很大,就只好用DFS了。


/*
PROG: clocks
ID: 06301031
LANG: C++
*/


#include 
<iostream>
#include 
<fstream>
#include 
<deque>
#include 
<vector>

using namespace std;

// A B C D E F G H I
// 0 1 2 3 4 5 6 7 8
const int moves[9][5= {{0,1,3,4,-1}{0,1,2,-1,-1}{1,2,4,5,-1}{0,3,6,-1,-1},
                         
{1,3,4,5,7},  {2,5,8,-1,-1}{3,4,6,7,-1}{6,7,8,-1,-1}{4,5,7,8,-1}}
;

static int minMoves = 50;
static int bestSolution[9];

void DFS(int status[], int method[], int t, int count) {
    
int i, j;
    
    
if (count > minMoves) {
        
return;
    }

    
bool flag = true;
    
for (i = 0; i < 9; i++{
        
if (status[i] != 12{
            flag 
= false;
            
break;
        }

    }

    
if (flag) {
        
if (count == minMoves) {
            
for (i = 0; i < 9; i++{
                
if (bestSolution[i] > method[i]) {
                    
return;
                }

                
if (bestSolution[i] < method[i]) {
                    
break;
                }

            }

        }

        minMoves 
= count;
        
for (int i = 0; i < 9; i++{
            bestSolution[i] 
= method[i];
        }

        
return;
    }

    
    
if (t >= 9{
        
return;
    }

    
    
for (i = 0; i < 4; i++{
        method[t] 
= i;
        
if (i == 0{
            DFS(status, method, t 
+ 1, count);
            
continue;
        }

        
        
// i != 0
        for (j = 0; j < 5; j++{
            
if (moves[t][j] < 0{
                
break;
            }

            status[moves[t][j]] 
+= 3;
            
if (status[moves[t][j]] > 12{
                status[moves[t][j]] 
= 3;
            }

        }

        DFS(status, method, t 
+ 1, count + i);
    }

    
    
// Turn the status again, to change it back.
    for (j = 0; j < 5; j++{
        
if (moves[t][j] < 0{
            
break;
        }

        status[moves[t][j]] 
+= 3;
        
if (status[moves[t][j]] > 12{
            status[moves[t][j]] 
= 3;
        }

    }

    method[t] 
= 0;
}


int main() {
    ifstream fin(
"clocks.in");
    ofstream fout(
"clocks.out");
    
int start[9], method[9];
    
int i, j;
    
for (i = 0; i < 9; i++{
        fin 
>> start[i];
    }

    
for (i = 0; i < 9; i++{
        method[i] 
= 0;
    }

    
for (i = 0; i < 9; i++{
        bestSolution[i] 
= 4;
    }

    
    DFS(start, method, 
00);
    
    vector
<int> answer;
    
for (i = 0; i < 9; i++{
        
if (bestSolution[i] > 0{
            
for (j = 0; j < bestSolution[i]; j++{
                answer.push_back(i 
+ 1);
            }

        }

    }

    fout 
<< answer[0];
    
for (i = 1; i < answer.size(); i++{
        fout 
<< " " << answer[i];
    }

    fout 
<< endl;
    fout.close();
    
    
return 0;
}


只有注册用户登录后才能发表评论。


网站导航: