poj 3414( 搜索 )
Pots
Description You are given two pots,having the volume ofAandBliters respectively. The following operations can be performed:
Write a program to find the shortest possible sequence of these operations that will yield exactlyCliters of water in one of the pots. Input On the first and only line are the numbersA,B,andC. These are all integers in the range from 1 to 100 andC≤max(A,B). Output The first line of the output must contain the length of the sequence of operationsK. The followingKlines must each describe one operation. If there are several sequences of minimal length,output any one of them. If the desired result can’t be achieved,the first and only line of the file must contain the word ‘impossible’. Sample Input 3 5 4 Sample Output 6 FILL(2) POUR(2,1) DROP(1) POUR(2,1) FILL(2) POUR(2,1) Source
Northeastern Europe 2002,Western Subregion
题目类型:搜索
题目描述:略
题目分析:略
代码如下:
#include <stdio.h> #include <string.h> #define N 101 struct Way { int prex; int prey; int kind; } way[N][N]; struct Point{ int x; int y; } queue[N*N*2],c,r; int answer[N*N]; int index = -1; int visit[N][N]; int va,vb,vc; void show(){ int i; char temp[6][10] = { "FILL(1)","FILL(2)","DROP(1)","DROP(2)","POUR(1,2)","POUR(2,1)"}; printf("%dn",index+1); for( i = index; i >= 0; i-- ){ printf("%sn",temp[answer[i]]); } } int bfs(){ int top = 0,end = 0,i; index = -1; memset(visit,sizeof(visit)); visit[0][0] = 1; queue[0].x = 0; queue[0].y = 0; while(top <= end){ c = queue[top]; for( i = 0; i < 6; i++){ switch( i ){ case 0: r.x = va; r.y = c.y; break; //fill 1 case 1: r.x = c.x; r.y = vb; break; //fill 2 case 2: r.x = 0; r.y = c.y; break; //drop 1 case 3: r.x = c.x; r.y = 0; break; //drop 2 case 4: //pour 1 2 if( c.x + c.y <= vb) { r.x = 0; r.y = c.x + c.y; } else { r.x = c.x - (vb - c.y); r.y = vb; } break; case 5: //pour 2 1 if( c.x + c.y <= va){ r.x = c.x + c.y; r.y = 0; } else { r.x = va; r.y = c.y - (va - c.x); } break; } if( visit[r.x][r.y] == 0){ if( r.x == vc || r.y == vc){ answer[++index] = i; int nx = c.x; int ny = c.y; int prex,prey; while( nx != 0 || ny != 0){ answer[++index] = way[nx][ny].kind; prex = way[nx][ny].prex; prey = way[nx][ny].prey; nx = prex; ny = prey; } return 1; } else { visit[r.x][r.y] = 1; queue[++end] = r; way[r.x][r.y].prex = c.x; way[r.x][r.y].prey = c.y; way[r.x][r.y].kind = i; } } } top++; } return -1; } int main() { while(scanf("%d%d%d",&va,&vb,&vc) != EOF){ if(bfs() == -1){ printf("impossiblen"); } else { show(); } } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |