首页 > ACM题库 > HDU-杭电 > hdu 2315 Shoot-out-BFS-[解题报告]hoj
2014
01-05

hdu 2315 Shoot-out-BFS-[解题报告]hoj

Shoot-out

问题描述 :

This is back in the Wild West where everybody is fighting everybody. In particular, there are n cowboys, each with a revolver. These are rather civilized cowboys, so they have decided to take turns firing their guns until only one is left standing. Each of them has a given probability of hitting his target, and they all know each other’s probability. Furthermore, they are geniuses and always know which person to aim at in order to maximize their winning chance, so they are indeed peculiar cowboys. If there are several equally good targets, one of those will be chosen at random. Note that a cowboy’s code of ethics forces him to do his best at killing one of his opponents, even if intentionally missing would have increased his odds (yes, this can happen!)

输入:

On the first line of the input is a single positive integer t, telling the number of test cases to follow. Each case consists of one line with an integer 2 ≤ n ≤ 13 giving the number of cowboys, followed by n positive integers giving hit percentages for the cowboys in the order of their turns.

输出:

On the first line of the input is a single positive integer t, telling the number of test cases to follow. Each case consists of one line with an integer 2 ≤ n ≤ 13 giving the number of cowboys, followed by n positive integers giving hit percentages for the cowboys in the order of their turns.

样例输入:

5
2 1 100
3 100 99 98
3 50 99 100
3 50 99 99
3 50 99 98

样例输出:

1.00 99.00
2.00 0.00 98.00
25.38 74.37 0.25
25.38 49.50 25.12
25.63 24.63 49.74


Hint 
Q: Does the cowboy know the other cowboys strategy of shooting?
A: Yes.


找了刘琳琳的code经过改动学习
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int board[26][26];
char ans[55];
int flag,p,q;
void travel(int i,int j,int s)
{
    if
(flag==1||board[i][j]==1)
return ;
board[i][j]=1;
ans[s*2]=i+’A';
ans[s*2+1]=j+’1′;
    if
(s==p*q-1)
    {
flag=1;
ans[s*2+2]=’\0′;
printf(“%s\n”,ans);
return;
    }
    if
(i-2>=0&&j-1>=0)
travel(i-2,j-1,s+1);
    if
(i-2>=0&&j+1<p)
travel(i-2,j+1,s+1);
    if
(i-1>=0&&j-2>=0)
travel(i-1,j-2,s+1);
    if
(i-1>=0&&j+2<p)
travel(i-1,j+2,s+1);
    if
(i+1<q&&j-2>=0)
travel(i+1,j-2,s+1);
    if
(i+1<q&&j+2<p)
travel(i+1,j+2,s+1);
    if
(i+2<q&&j-1>=0)
travel(i+2,j-1,s+1);
    if
(i+2<q&&j+1<p)
travel(i+2,j+1,s+1);
board[i][j]=0;
}
int main()
{
    int
t,cases=1,i,j;
scanf(“%d”,&t);
    while
(t–)
    {
scanf(“%d %d”,&p,&q);
flag=0;
printf(“Scenario #%d:\n”,cases++);
for (i=0;i<q;i++)
{
for (j=0;j<p;j++)
{
memset(board,0,sizeof(board));
travel(i,j,0);
if (flag)
break;
}
if (flag)
break;
}
if (!flag)
printf(“impossible\n”);
printf(“\n”);
    }
    return
0;
}
 又找到精简版
#include <iostream>
using namespace std;
int N, M, set;
bool Visited[26][26];
bool Find;
int step;
int A[] = {-2, -2, -1, -1, 1, 1, 2, 2};
int B[] = {-1, 1, -2, 2, -2, 2, -1, 1};
struct Node
{
int x, y;
}Path[26];
bool Valid(const int x, const int y)
{
if(x >= 0 && x
< M && y
>= 0 && y
< N)
return true;
return false;
}
void search(int x, int y)
{
if(Find)
return;
Visited[x][y] = true;
    Path[step].x
= x, Path[step].y = y;
if(step == N * M – 1)
{
Find = true;
return;
}
for(int i = 0; i < 8; i++)
{
int a = x + A[i];
int b = y + B[i];
if(Valid(a, b) && Visited[a][b] ==
false)
{
step++;
search(a, b);
step–; //
}
}
Visited[x][y] = false;
}
int main()
{
scanf(“%d”, &set);
for(int i = 1; i <= set; i++)
{
Find = false;
memset(Visited, false, sizeof(Visited));
scanf(“%d %d”, &N, &M);
printf(“Scenario #%d:\n”, i);
search(0, 0);
if(Find)
for(int i = 0; i < N * M; i++)
printf(“%c%d”, Path[i].x + ‘A’, Path[i].y + 1);
else
printf(“impossible”);
printf(“\n”);
if(i < set)
printf(“\n”);
}
return 0;
}
解题参考:http://blog.sina.com.cn/s/blog_49f9e4fc0100bt51.html


  1. for(int i=1; i<=m; i++){
    for(int j=1; j<=n; j++){
    dp = dp [j-1] + 1;
    if(s1.charAt(i-1) == s3.charAt(i+j-1))
    dp = dp[i-1] + 1;
    if(s2.charAt(j-1) == s3.charAt(i+j-1))
    dp = Math.max(dp [j - 1] + 1, dp );
    }
    }
    这里的代码似乎有点问题? dp(i)(j) = dp(i)(j-1) + 1;这个例子System.out.println(ils.isInterleave("aa","dbbca", "aadbbcb"));返回的应该是false

  2. “再把所有不和该节点相邻的节点着相同的颜色”,程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的

  3. 第二块代码if(it != mp.end())应改为if(it != mp.end() && (i+1)!=(it->second +1));因为第二种解法如果数组有重复元素 就不正确

  4. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  5. “再把所有不和该节点相邻的节点着相同的颜色”,程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的