首页 > 代码库 > UVA 322 ships (POJ 1138)
UVA 322 ships (POJ 1138)
题目地址：
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=258
http://poj.org/problem?id=1138
题目描述：
Ships
| Ships |
Probably everyone who ever attended school knows the game where two opposing players place a set of ships on a sheet of paper and try to eliminate each other‘s ships by guessing their location.
In our version of the game, your opponent has distributed the following seven ship patterns over a rectangular grid of squares:
xx xx xx x x x
xx xx xx xxx xxx xxx xxxxEach ship pattern covers exactly four squares. The patterns may be rotated but not mirrored. All patterns are guaranteed to be placed completely within the boundaries of the rectangle and not to overlap each other, whereas touching another pattern or the border is allowed.
We assume that we are in the middle of the game and that several squares have already been uncovered. You will be given a rectangular grid of squares representing your current knowledge about the positions of your enemy‘s ships. Every square is marked by one of the following characters:
- `x‘ if a ship covers the square
- `o‘ if no ship covers the square
- `.‘ if the square has not yet been uncovered
Given that information, you are to decide whether you can determine all remaining `x‘ squares with at most one miss, i.e. whether you could uncover the `.‘ squares without getting more than one `o‘ square before you had all `x‘ squares uncovered. This means you are allowed to hit a `o‘ if then the solution becomes unique.
Input
The input file contains several game situations. Every test case starts with a line containing two integers w and h. These define width and height of the game rectangle, where 
.
Each of the next h lines contains a string of w characters. Each of these characters is either `x‘, `o‘ or `.‘, depending on the state of the corresponding square.
A blank line separates each game from the next. The input file ends with a game having w = 0 and h = 0. This game should not be processed.
Output
For each test case you should first output a line containing the number of the game, followed by a line containing either `yes.‘ (if you can determine all `x‘ with at most one miss) or `no.‘ (if you cannot determine all `x‘ without at least two misses).
Output a blank line after every game.
Sample Input
10 10 .x..x..... oooooxoooo oxooxxx... xxoooooo.. xoooxooo.. ooxxxxoo.. oooooxxoox ooooooxoox ooooooooxx oooooooooo 0 0
Sample Output
Game #1 yes.
题意：
电脑最多只有一次失败的机会（或者0次失败）来打中（揭开）所有的‘x’。
题解：
这题卡了我很久，今天终于AC了。
分析：
其实这题主要了两个主要的问题需要解决。
1、得到输入的图形，如何得到所有完备的7船模型？？？这里的7船模型指的是，我们揭开所有的7只船的所有模式在图中，即图中的方格只能是‘o’或者‘x’，没有不确定的‘.‘了，模型有7种，模式是一种模型通过不同的旋转变化而来。
其实这里我们可以用DFS 7种模型的所有模式在图中尝试匹配，遍历第一种模型中的所有模式，如果能够匹配，那我们DFS下一种模型；如果匹配到第7种模型，并且能匹配成功，那么我们就得到了其中一种可能的完备7船模型图（有很多中可能的7船模型图），把他保存下来，以便后面的步骤用来确定是yes还是no的最终答案。
2、在得到了所有可能的7船模型后，我们如何通过这些可能的7船模型来得出最终的yes还是no呢？？
其实这里我先以题中的样例分析过程来展示具体是如何得出yes和no的：
首选，样例的形式如下所示：
.x..x.....
oooooxoooo
oxooxxx...
xxoooooo..
xoooxooo..
ooxxxxoo..
oooooxxoox
ooooooxoox
ooooooooxx
oooooooooo
这个我们不难发现这样一个输入图，一共能得出3种可能的7船完备图（自己在纸上画画即可）：
oxxxxooooo
oooooxoooo
oxooxxxooo
xxoooooooo
xoooxoooxx
ooxxxxooxx
oooooxxoox
ooooooxoox
ooooooooxx
oooooooooo
oxooxooooo
oooooxoooo
oxooxxxooo
xxooooooxx
xoooxoooxx
ooxxxxoooo
oooooxxoox
ooooooxoox
ooooooooxx
oooooooooo
oxxxxooooo
oooooxoooo
oxooxxxoxx
xxooooooxx
xoooxooooo
ooxxxxoooo
oooooxxoox
ooooooxoox
ooooooooxx
oooooooooo
这样我们得到了上述3种的完备图形，即无论输入图形怎么变化，只可能是这3种可能。那么电脑是如何通过分析这3种可能的7船完备图来得出yes还是no呢？？
通过仔细观察我们不难发现，综合这3种船模型，我们发现大部分点在3种模型中的点是固定不变的，而有一部分点是在3种模型的点是变化的，即可能在一种模型中是‘x‘而在另一种模型中是‘o‘。显然电脑能得出yes和no，肯定来自于这些变化的点，我不妨把变化的点提出来，这里样例中变化的点有8个：
..
..
..
分别有以下可能的分布：
oo
oo
xx
xx
oo
xx
xx
oo
xx
xx
oo
oo
那么o我们来看电脑怎么据此得出yes或者no的，首选电脑选择8个点中间的4个点的任意一点揭开，这里我们以中间4个点的坐下点为例，相对于8个点的坐标是（2，0）
1、如果这个点是‘o‘，那么显然我们可以排除第一种模型和第二种模型，显然就只有第三种模型，所以电脑这里仅失误了一次就能确定是哪个模型了。
2、如果这个点是‘x’，那么我们可以把第三种模型排除掉，由于我们还有一次打偏的机会（揭开的点为‘o‘），所以o我们继续取，这时候我们取最后一行的两点的任意点，如果是‘x‘那么肯定是第一种，电脑没有失误一次得到一个确定模型；如果是‘o‘，那么肯定是第二种，那么电脑也仅失误一次得到一种确定的模型图。
综上，电脑都能符合要求（仅失误一次或0次）得到确定的所有可能的7船模型。所以是yes；反之如果在其中 一个过程中电脑不能获得，那就直接是no了。
这里我们肯定在想，电脑是如何确定取哪个点来作为‘x‘或者‘o‘，来分析的呢，就如上面，为什么电脑一开始一定要选择中间的4个点呢？？
其实这里我们可以通过这些点在所有可能的7船模型中出现‘x‘的数量和出现‘o‘的数量来区分中间4个点和两端的4个点：
中间4点->1*o,2*x 两端4点->2*o,1*x
即中间4点在所有可能模型中出现1次‘o‘，出现2次‘x‘。
这样电脑确定yes和no的策略为：每次选取出现o最少次数的点作为分析点，为‘x‘分析下去，为‘o‘分析下去；如果所有的分析，电脑仅在失误一次的情况下，剩下的完备7船模型都是小于等于1的，那么表示电脑能够确定，为yes，反之就为no。
数据结构：
因为这些非固定的点实在太重要，我们不妨对这些点做一个定义，这里我定义非固定点为歧义点，反之则是非歧义点。
我们定义：在图形中的某些点，他们在所有可能的7船模型中会因不同的模型，其值（‘x‘ or ‘o‘）也会不同，我们称这些点为歧义点，反之为非歧义点。
歧义点/非歧义点的数据结构：
int m;(表示在所有可能的7船模型中出现‘o‘的次数)
int n;（表示在所有可能中出现‘n‘的次数）
显然m>0&&n>0为歧义点，反之则是非歧义点。
算法：
一、通过DFS得到所有的可能的完备7船模型：
1、DFS一种模型
2、遍历一种模型的所有模式，如果匹配
3、DFS下一种模型
4、如果匹配到7中模型都能匹配，发现一种可能的完备7船模型，保存。
二、得到所有可能的7船模型，构造歧义点/非歧义点：
1、遍历所有的7船模型
2、遍历一个可能的7船模型的所有方格
3、构造歧义点/非歧义点，如果是‘x‘则n++，如果是‘o‘则m++
三、DFS歧义点/非歧义点表，确定最终的yes或者no
1、选择最小的m的歧义点（注意一定要是歧义点）作为DFS点。
2、如果此点是‘o‘，剔除这个点是‘x‘的7船模型（并且更新歧义点/非歧义点信息），然后DFS下一个点。
3、如果此点是‘x‘，剔除这个点是‘o‘的7船模型（并且更新歧义点/非歧义点信息），然后DFS下一个点。
4、如果仅用了一次‘o’或者0次‘o‘作为DFS点，并且可能的7船模型数量小于等于1（即表示电脑可以确定了，或者所有点都是非歧义点了），那么表示电脑在这个分支可以确定7船模型。
5、如果电脑在所有分支都能这样确定，则输出yes，反之输出no（即只要有一个分支不能确定，就全盘都是no）
剪枝：
1、‘x‘的数量一定是28=4*7。（7中模型，每个模型肯定占4个‘x‘，在遍历中记录‘x‘的数量，一旦超过28，直接回退这个分支，没必要再深搜下去）
2、7船完备模型一定要是每种模式仅出现一次，且必须出现一次，不能重复，也不能缺漏。
3、如果得到的可能的7船模型图的数量大于h*w，那么直接输出no。（这里我们假设，就算我们以h*w方阵的每个点作为一次miss（即该点为‘o‘），最多能得到h*w个不同的7船完备模型图，如果我们得到的所有可能的7船模型图数量大于了h*w；那么必然存在一个点或多个点，我们以此作为miss，作为失误的‘o‘，肯定对应两种及以上的7船完备模型，这样肯定就不能仅满足一次失误的条件，所以肯定是no。）
注意：
1、更多详细设计见代码。
2、这里UVA的输入格式与POJ的输入格式是不同的，其中
UVA的是：w h（先输入w再输入h） POJ的是：h w（先输入h再输入w） 不然会得到WA
3、我这里的代码是UVA的版本（即先w再h），如果要改成POJ的，只需要在输出的地方把我代码的H和W调换一下就行了。
代码：
#include<stdio.h>
#include<string.h>
#define LL 20
#define X 28 //x sum count = 7*4
typedef struct pot
{
int m;//the number of the 'o'
int n;//the number of the 'x'
bool is_various;//if m > 0 and n > 0 then is_various = true
int x;//the coordinate of x,(0,0) is origin point
int y;//the coordinate of y,(0,0) is origin point
pot()
{
m=0;
n=0;
is_various=false;
x=0;
y=0;
}
}pot,*pot_link;
typedef struct grid
{
int r;
int c;
pot val[LL][LL];
grid()
{
r=0;
c=0;
}
}grid,*grid_link;
char grids[500][LL][LL];//save the possible complete grid (no '.' only 'o' or 'x')
int cnt=0;//count of the grids
int used_grids[500]={0};//0 is not visited x>0 is cur==x we visited it
char in_grid[LL][LL];//input grid
grid pot_grid;//save the cases of pot in grid
int W=0,H=0;//the input grid 's width and height
int R=0,C=0;//the input of row and col
int cases=0;
int x_cnt=0;//x count of input
int o_cnt=0;//o count of input
int i_cnt=0;//. count of input and x_cnt + o_cnt + i_cnt == W * H
//the 7 kinds of boat all patterns include per kind and rotate 4 times
char patterns[19][10][10]=
{
{
"xx",//1 kind -> 1 pattern
"xx"
},
{
"xx",//1 kind-> 2 patterns
" xx"
},
{
" x",
"xx",
"x"
},
{
" xx",//1 kind -> 2 patterns
"xx"
},
{
"x ",
"xx",
" x"
},
{
"x",//1 kind -> 4 patterns
"xxx"
},
{
"xx",
"x",
"x"
},
{
"xxx",
" x"
},
{
" x",
" x",
"xx"
},
{
" x ",//1 kind -> 4 patterns
"xxx"
},
{
"x",
"xx",
"x"
},
{
"xxx",
" x"
},
{
" x",
"xx",
" x"
},
{
" x",//1 kind -> 4 patterns
"xxx"
},
{
"x",
"x",
"xx"
},
{
"xxx",
"x"
},
{
"xx",
" x",
" x"
},
{
"xxxx"//1 kind -> 2 patterns
},
{
"x",
"x",
"x",
"x"
}
};
int kind_cnt[7]={1,2,2,4,4,4,2};//kind count of the 7 kind of boats, i(begin with 0) kind jth pattern is patterns[kind_cnt[0]+kind_cnt[1]+......+kind_cnt[i-1]+j]
int kind_ind[7]={0,1,3,5,9,13,17};//kind index in the patterns array
//in_grid deal -> ('z','x'->'x' 'o','.'->'o')
int insert_grid()
{
//insert the in_grid to grids
for(int i=0;i<=R-1;i++)
{
for(int j=0;j<=C-1;j++)
{
if(in_grid[i][j]=='.') {grids[cnt][i][j]='o';}
else if(in_grid[i][j]>=0&&in_grid[i][j]<=6) {grids[cnt][i][j]='x';}
else {grids[cnt][i][j]=in_grid[i][j];}
}
}
cnt++;
if(cnt>=1000) {cnt--;}//exceed the boundary
return(0);
}
//place next patterns and insert the complete grid into the grids
int DFS_kind(int cur)
{
if(x_cnt>28) {return(0);}
if(cnt>R*C) {return(-1);}
if(cur>=7)
{
int x_c=0;
for(int i=0;i<=R-1;i++)
{
for(int j=0;j<=C-1;j++)
{
if(in_grid[i][j]=='x'||(in_grid[i][j]>=0&&in_grid[i][j]<=6)) {x_c++;}
}
}
if(x_c==28)//4(point) * 7(boat pattern)
{
insert_grid();//in_grid -> ('z','x'->'x' 'o','.'->'o') and not insert the repeat gird
}
}
else
{
//scan this kind of all specific patterns
for(int k=0;k<=kind_cnt[cur]-1;k++)
{
int pat_ind=kind_ind[cur]+k;
//translation the pattern's origin point from (0,0) .... to ... (R-1,C-1)
for(int nexti=0;nexti<=R-1;nexti++)
{
for(int nextj=0;nextj<=C-1;nextj++)
{
//scan the patterns and in_grid by nexti,nextj
int i=0,j=0;
int match_cnt=0;
//record the previous value to reverse
int pre_x[5]={0};
int pre_y[5]={0};
char pre_char[5]={0};
while(i<=4-1&&j<=4-1)
{
char ch=patterns[pat_ind][i][j];
if(ch!='\0')
{
if(ch=='x')
{
if(nexti+i>R-1||nextj+j>C-1) {break;}//exceed boundary,it must no be matched
if(in_grid[nexti+i][nextj+j]=='x'||in_grid[nexti+i][nextj+j]=='.')//matched
{
if(in_grid[nexti+i][nextj+j]=='.') {x_cnt++;}
pre_x[match_cnt]=nexti+i;
pre_y[match_cnt]=nextj+j;
pre_char[match_cnt]=in_grid[nexti+i][nextj+j];
match_cnt++;
in_grid[nexti+i][nextj+j]=cur;//the current cur turn we mark it to indicate that this point have been visited at curth turn
}
else {break;}//the in_grid[nexti+i][nextj+j]=='o' or 'z',not matched
}
}
j++;
if(j>4-1)
{
j=0;
i++;
}
}
if(match_cnt==4)//is matched this kind dfs next kind
{
int flag=DFS_kind(cur+1);
if(flag==-1) {return(-1);}
}
//reverse the z -> x or .
for(int ci=0;ci<=match_cnt-1;ci++) {in_grid[pre_x[ci]][pre_y[ci]]=pre_char[ci];if(pre_char[ci]=='.') {x_cnt--;}}
}
}
}
}
return(0);
}
//construct the pot_grid
int constr_pot()
{
//construct the pot_grid
for(int c=0;c<=cnt-1;c++)
{
for(int i=0;i<=R-1;i++)
{
for(int j=0;j<=C-1;j++)
{
if(grids[c][i][j]=='x') {pot_grid.val[i][j].n++;}
else {pot_grid.val[i][j].m++;}
}
}
}
//construct the is_various
for(int i=0;i<=R-1;i++)
{
for(int j=0;j<=C-1;j++)
{
if(pot_grid.val[i][j].m>0&&pot_grid.val[i][j].n>0) {pot_grid.val[i][j].is_various=true;}
}
}
return(0);
}
//sub the char c in the all min_m.x min_m.y in the grids
int sub_grids(pot min_m,char ch,int cur)
{
for(int c=0;c<=cnt-1;c++)
{
if(!used_grids[c]&&grids[c][min_m.x][min_m.y]==ch)
{
used_grids[c]=cur;
for(int i=0;i<=R-1;i++)
{
for(int j=0;j<=C-1;j++)
{
if(grids[c][i][j]=='x') {pot_grid.val[i][j].n--;}
else {pot_grid.val[i][j].m--;}
if(!(pot_grid.val[i][j].m>0&&pot_grid.val[i][j].n>0)) {pot_grid.val[i][j].is_various=false;}
}
}
}
}
return(0);
}
//add the char c in the used_grids[x] == cur in the pot_grid,reverse the sub
int add_grids(int cur)
{
for(int c=0;c<=cnt-1;c++)
{
if(used_grids[c]==cur)
{
used_grids[c]=0;
for(int i=0;i<=R-1;i++)
{
for(int j=0;j<=C-1;j++)
{
if(grids[c][i][j]=='x') {pot_grid.val[i][j].n++;}
else {pot_grid.val[i][j].m++;}
if(pot_grid.val[i][j].m>0&&pot_grid.val[i][j].n>0) {pot_grid.val[i][j].is_various=true;}
}
}
}
}
return(0);
}
//dfs the pot_grid and eliminate the various pot,the use_o must <= 1 , cur is the count of turn it must > 0
int DFS_pot(int cur,int use_o)
{
if(use_o>=2) {return(0);}//have used 'o' twice or more times then it is false
//find various pot , minimum m
pot min_m;
int flag=0;
int mark=0;
min_m.m=1000;
for(int i=0;i<=R-1;i++)
{
for(int j=0;j<=C-1;j++)
{
if(pot_grid.val[i][j].is_various)
{
flag=1;
if(pot_grid.val[i][j].m<min_m.m)
{
min_m.m=pot_grid.val[i][j].m;
min_m.n=pot_grid.val[i][j].n;
min_m.x=i;
min_m.y=j;
}
}
}
}
if(!flag) {return(1);}//no 'o' we direct get yes
//suppose the min_m pot is 'o' so we eliminate the 'x' of grids
sub_grids(min_m,'x',cur);
//dfs
mark=DFS_pot(cur+1,use_o+1);
if(!mark) {return(0);}//if false then all false
//reverse the suppose of the min_m pot is 'o'
add_grids(cur);
//suppose the min_m pot is 'x'
sub_grids(min_m,'o',cur);
//dfs
mark=DFS_pot(cur+1,use_o);
if(!mark) {return(0);}//if false then all false
//reverse the suppose of the min_m pot is 'x'
add_grids(cur);
return(1);
}
int main()
{
//note!! this problem in uva(322) is input is W H but in poj(1138) is H W, current version is for uva
while(scanf("%d%d",&W,&H)!=EOF&&(W+H)>0)
{
R=H;
C=W;
cnt=0;
x_cnt=o_cnt=i_cnt=0;
pot_grid.r=R;
pot_grid.c=C;
memset(grids,'\0',sizeof(grids));
memset(used_grids,0,sizeof(used_grids));
for(int i=0;i<=R-1;i++)//initialize the pot_grid
{
for(int j=0;j<=C-1;j++)
{
pot_grid.val[i][j].is_various=false;
pot_grid.val[i][j].m=pot_grid.val[i][j].n=pot_grid.val[i][j].x=pot_grid.val[i][j].y=0;
}
}
printf("Game #%d\n",++cases);
for(int i=0;i<=R-1;i++)
{
scanf("%s",in_grid[i]);
for(int j=0;j<=C-1;j++)
{
switch(in_grid[i][j])
{
case 'x':
x_cnt++;
break;
case 'o':
o_cnt++;
break;
case '.':
i_cnt++;
break;
}
}
}
//prune
if(x_cnt>28)
{
printf("no.\n\n");
continue;
}
//dfs the input grid
DFS_kind(0);//place next patterns and insert the complete grid into the grids
//construction pot_grid
constr_pot();
//dfs the pot_grid and get the yes or no
if(cnt>0&&cnt<=R*C&&DFS_pot(1,0)) printf("yes.\n\n");
else printf("no.\n\n");
}
return(0);
}
UVA 322 ships (POJ 1138)