hdu 2531 Catch him (bfs)
Catch him
**Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 664 Accepted Submission(s): 307
**
Problem Description
在美式足球中，四分卫负责指挥整只球队的进攻战术和跑位，以及给接球员传球的任务。四分卫是一只球队进攻组最重要的球员，而且一般身体都相对比较弱小，所以通常球队会安排5-7名大汉来保护他，其中站在四分卫前方、排成一线的5名球员称为进攻锋线，他们通常都是135公斤左右的壮汉。
对防守方来说，攻击对手的四分卫当然是最直接的限制对手进攻的方法。如果效果好，就可以在对方四分卫传球之前将其按翻在地，称之为擒杀。擒杀是最好的鼓舞防守队士气的方法，因为对方连传球的机会都没有，进攻就结束了，还必须倒退一些距离开球。凶狠的擒杀甚至能够将对方的四分卫弄伤，从而迫使对方更换这个进攻核心。
在本题中，输入给出准备擒杀四分卫的防守球员的位置、对方每个进攻锋线球员的位置以及对方四分卫的位置，你的任务是求出这名准备擒杀的防守球员至少要移动多少步，才能够擒杀对方四分卫。
假设对方进攻锋线和四分卫在这个过程中都不会移动。只有1名防守球员，防守球员只要碰到对方四分卫就算擒杀。
所有的球员都是一块连续的、不中空的2维区域。防守球员不可以从进攻锋线的身体上穿过，也不可以从界外穿过(只能走空地)。
防守队员不可以转动身体，只能平移。防守队员的身体所有部分向同一个方向(上、下、左、右)移动1格的过程叫做1步。
Input
输入包含多组数据。每组数据第一行都是两个整数H，W(0输入保证符合上面的条件。防守球员的身体总共不超过20格。
Output
对每组数据，输出包含擒杀所需最少步数的一行。如果不能擒杀，输出带'Impossible'的一行。
Sample Input
6 6 .Q.... QQ..OO .OO..O ...O.O OO.O.. ....DD 7 7 .Q..... QQ.OOO. ...O... O...... OO..OO. .O..... .....DD 0 0
Sample Output
Impossible 9
这题最开始昨天晚上看到直接懵了．．．
人的身体有多部分＝＝ 还不规则．．怎么搞．．．
然后昨天睡觉的时候灵光一现（大雾
今天起来搞搞搞...
竟然1A．．．．爽坏了
其实很简单．
就是只考虑一个点．
其他点存与最初这个点的相对位移．
然后只做这第一个点的bfs
只不过判断条件的时候要判断所有点的
以及是否摸（？）到四分卫的时候也要判断多个点的就好了．
<span style="color: #008080;"> 1</span> <span style="color: #008000;">/*</span><span style="color: #008000;">************************************************************************
</span><span style="color: #008080;"> 2</span> <span style="color: #008000;"> > File Name: code/hdu/2531.cpp
</span><span style="color: #008080;"> 3</span> <span style="color: #008000;"> > Author: 111qqz
</span><span style="color: #008080;"> 4</span> <span style="color: #008000;"> > Email: rkz2013@126.com
</span><span style="color: #008080;"> 5</span> <span style="color: #008000;"> > Created Time: 2015年10月11日 星期日 23时14分43秒
</span><span style="color: #008080;"> 6</span> <span style="color: #008000;"> ***********************************************************************</span><span style="color: #008000;">*/</span>
<span style="color: #008080;"> 7</span>
<span style="color: #008080;"> 8</span> #include<iostream>
<span style="color: #008080;"> 9</span> #include<iomanip>
<span style="color: #008080;"> 10</span> #include<cstdio>
<span style="color: #008080;"> 11</span> #include<algorithm>
<span style="color: #008080;"> 12</span> #include<cmath>
<span style="color: #008080;"> 13</span> #include<cstring>
<span style="color: #008080;"> 14</span> #include<<span style="color: #0000ff;">string</span>>
<span style="color: #008080;"> 15</span> #include<map>
<span style="color: #008080;"> 16</span> #include<<span style="color: #0000ff;">set</span>>
<span style="color: #008080;"> 17</span> #include<queue>
<span style="color: #008080;"> 18</span> #include<vector>
<span style="color: #008080;"> 19</span> #include<stack>
<span style="color: #008080;"> 20</span> #include<cctype>
<span style="color: #008080;"> 21</span>
<span style="color: #008080;"> 22</span> <span style="color: #0000ff;">#define</span> yn hez111qqz
<span style="color: #008080;"> 23</span> <span style="color: #0000ff;">#define</span> j1 cute111qqz
<span style="color: #008080;"> 24</span> <span style="color: #0000ff;">#define</span> ms(a,x) memset(a,x,sizeof(a))
<span style="color: #008080;"> 25</span> <span style="color: #0000ff;">using</span> <span style="color: #0000ff;">namespace</span><span style="color: #000000;"> std;
</span><span style="color: #008080;"> 26</span> <span style="color: #0000ff;">const</span> <span style="color: #0000ff;">int</span> dx4[<span style="color: #800080;">4</span>]={<span style="color: #800080;">1</span>,<span style="color: #800080;">0</span>,<span style="color: #800080;">0</span>,-<span style="color: #800080;">1</span><span style="color: #000000;">};
</span><span style="color: #008080;"> 27</span> <span style="color: #0000ff;">const</span> <span style="color: #0000ff;">int</span> dy4[<span style="color: #800080;">4</span>]={<span style="color: #800080;">0</span>,-<span style="color: #800080;">1</span>,<span style="color: #800080;">1</span>,<span style="color: #800080;">0</span><span style="color: #000000;">};
</span><span style="color: #008080;"> 28</span> typedef <span style="color: #0000ff;">long</span> <span style="color: #0000ff;">long</span><span style="color: #000000;"> LL;
</span><span style="color: #008080;"> 29</span> typedef <span style="color: #0000ff;">double</span><span style="color: #000000;"> DB;
</span><span style="color: #008080;"> 30</span> <span style="color: #0000ff;">const</span> <span style="color: #0000ff;">int</span> inf = <span style="color: #800080;">0x3f3f3f3f</span><span style="color: #000000;">;
</span><span style="color: #008080;"> 31</span> <span style="color: #0000ff;">const</span> <span style="color: #0000ff;">int</span> N=1E2+<span style="color: #800080;">5</span><span style="color: #000000;">;
</span><span style="color: #008080;"> 32</span> <span style="color: #0000ff;">int</span><span style="color: #000000;"> w,h;
</span><span style="color: #008080;"> 33</span> <span style="color: #0000ff;">char</span><span style="color: #000000;"> maze[N][N];
</span><span style="color: #008080;"> 34</span> <span style="color: #0000ff;">bool</span><span style="color: #000000;"> v[N][N];
</span><span style="color: #008080;"> 35</span> <span style="color: #0000ff;">int</span><span style="color: #000000;"> cnt ;
</span><span style="color: #008080;"> 36</span> <span style="color: #0000ff;">int</span> fx[<span style="color: #800080;">30</span><span style="color: #000000;">];
</span><span style="color: #008080;"> 37</span> <span style="color: #0000ff;">int</span> fy[<span style="color: #800080;">30</span><span style="color: #000000;">];
</span><span style="color: #008080;"> 38</span> <span style="color: #0000ff;">struct</span><span style="color: #000000;"> node
</span><span style="color: #008080;"> 39</span> <span style="color: #000000;">{
</span><span style="color: #008080;"> 40</span> <span style="color: #0000ff;">int</span><span style="color: #000000;"> x,y;
</span><span style="color: #008080;"> 41</span> <span style="color: #0000ff;">int</span><span style="color: #000000;"> d;
</span><span style="color: #008080;"> 42</span> <span style="color: #0000ff;">bool</span><span style="color: #000000;"> ok()
</span><span style="color: #008080;"> 43</span> <span style="color: #000000;"> {
</span><span style="color: #008080;"> 44</span> <span style="color: #0000ff;">if</span> (x<<span style="color: #800080;">0</span>||y<<span style="color: #800080;">0</span>||x>=w||y>=h) <span style="color: #0000ff;">return</span> <span style="color: #0000ff;">false</span><span style="color: #000000;">;
</span><span style="color: #008080;"> 45</span> <span style="color: #0000ff;">if</span> (maze[x][y]==<span style="color: #800000;">'</span><span style="color: #800000;">O</span><span style="color: #800000;">'</span>) <span style="color: #0000ff;">return</span> <span style="color: #0000ff;">false</span><span style="color: #000000;">;
</span><span style="color: #008080;"> 46</span> <span style="color: #0000ff;">if</span> (v[x][y]) <span style="color: #0000ff;">return</span> <span style="color: #0000ff;">false</span><span style="color: #000000;">;
</span><span style="color: #008080;"> 47</span>
<span style="color: #008080;"> 48</span> <span style="color: #0000ff;">for</span> ( <span style="color: #0000ff;">int</span> i =<span style="color: #800080;">2</span> ; i <= cnt ; i++<span style="color: #000000;">)
</span><span style="color: #008080;"> 49</span> <span style="color: #000000;"> {
</span><span style="color: #008080;"> 50</span> <span style="color: #0000ff;">int</span> xx = x +<span style="color: #000000;"> fx[i];
</span><span style="color: #008080;"> 51</span> <span style="color: #0000ff;">int</span> yy = y +<span style="color: #000000;"> fy[i];
</span><span style="color: #008080;"> 52</span> <span style="color: #0000ff;">if</span> (xx<<span style="color: #800080;">0</span>||yy<<span style="color: #800080;">0</span>||xx>=w||yy>=h) <span style="color: #0000ff;">return</span> <span style="color: #0000ff;">false</span><span style="color: #000000;">;
</span><span style="color: #008080;"> 53</span> <span style="color: #0000ff;">if</span> (maze[xx][yy]==<span style="color: #800000;">'</span><span style="color: #800000;">O</span><span style="color: #800000;">'</span>) <span style="color: #0000ff;">return</span> <span style="color: #0000ff;">false</span><span style="color: #000000;">;
</span><span style="color: #008080;"> 54</span> <span style="color: #000000;"> }
</span><span style="color: #008080;"> 55</span> <span style="color: #0000ff;">return</span> <span style="color: #0000ff;">true</span><span style="color: #000000;">;
</span><span style="color: #008080;"> 56</span> <span style="color: #000000;"> }
</span><span style="color: #008080;"> 57</span>
<span style="color: #008080;"> 58</span> <span style="color: #0000ff;">bool</span> <span style="color: #0000ff;">get</span><span style="color: #000000;">()
</span><span style="color: #008080;"> 59</span> <span style="color: #000000;"> {
</span><span style="color: #008080;"> 60</span> <span style="color: #0000ff;">if</span> (maze[x][y]==<span style="color: #800000;">'</span><span style="color: #800000;">Q</span><span style="color: #800000;">'</span>) <span style="color: #0000ff;">return</span> <span style="color: #0000ff;">true</span><span style="color: #000000;">;
</span><span style="color: #008080;"> 61</span> <span style="color: #0000ff;">for</span> ( <span style="color: #0000ff;">int</span> i = <span style="color: #800080;">2</span> ; i <= cnt ; i++<span style="color: #000000;">)
</span><span style="color: #008080;"> 62</span> <span style="color: #000000;"> {
</span><span style="color: #008080;"> 63</span> <span style="color: #0000ff;">int</span> xx = x +<span style="color: #000000;"> fx[i];
</span><span style="color: #008080;"> 64</span> <span style="color: #0000ff;">int</span> yy = y +<span style="color: #000000;"> fy[i];
</span><span style="color: #008080;"> 65</span> <span style="color: #0000ff;">if</span> (maze[xx][yy]==<span style="color: #800000;">'</span><span style="color: #800000;">Q</span><span style="color: #800000;">'</span><span style="color: #000000;">)
</span><span style="color: #008080;"> 66</span> <span style="color: #000000;"> {
</span><span style="color: #008080;"> 67</span> <span style="color: #0000ff;">return</span> <span style="color: #0000ff;">true</span><span style="color: #000000;">;
</span><span style="color: #008080;"> 68</span> <span style="color: #000000;"> }
</span><span style="color: #008080;"> 69</span> <span style="color: #000000;"> }
</span><span style="color: #008080;"> 70</span> <span style="color: #0000ff;">return</span> <span style="color: #0000ff;">false</span><span style="color: #000000;">;
</span><span style="color: #008080;"> 71</span> <span style="color: #000000;"> }
</span><span style="color: #008080;"> 72</span> <span style="color: #000000;">}s;
</span><span style="color: #008080;"> 73</span>
<span style="color: #008080;"> 74</span> <span style="color: #0000ff;">bool</span><span style="color: #000000;"> bfs()
</span><span style="color: #008080;"> 75</span> <span style="color: #000000;">{
</span><span style="color: #008080;"> 76</span>
<span style="color: #008080;"> 77</span> queue<node><span style="color: #000000;">q;
</span><span style="color: #008080;"> 78</span> <span style="color: #000000;"> q.push(s);
</span><span style="color: #008080;"> 79</span>
<span style="color: #008080;"> 80</span> <span style="color: #0000ff;">while</span> (!<span style="color: #000000;">q.empty())
</span><span style="color: #008080;"> 81</span> <span style="color: #000000;"> {
</span><span style="color: #008080;"> 82</span> node pre =<span style="color: #000000;"> q.front();q.pop();
</span><span style="color: #008080;"> 83</span>
<span style="color: #008080;"> 84</span> <span style="color: #008000;">//</span><span style="color: #008000;"> printf("x: %d y: %d d: %d n",pre.x,pre.y,pre.d);</span>
<span style="color: #008080;"> 85</span>
<span style="color: #008080;"> 86</span> <span style="color: #0000ff;">if</span> (pre.<span style="color: #0000ff;">get</span><span style="color: #000000;">())
</span><span style="color: #008080;"> 87</span> <span style="color: #000000;"> {
</span><span style="color: #008080;"> 88</span> printf(<span style="color: #800000;">"</span><span style="color: #800000;">%dn</span><span style="color: #800000;">"</span><span style="color: #000000;">,pre.d);
</span><span style="color: #008080;"> 89</span> <span style="color: #0000ff;">return</span> <span style="color: #0000ff;">true</span><span style="color: #000000;">;
</span><span style="color: #008080;"> 90</span> <span style="color: #000000;"> }
</span><span style="color: #008080;"> 91</span>
<span style="color: #008080;"> 92</span> <span style="color: #0000ff;">for</span> ( <span style="color: #0000ff;">int</span> i = <span style="color: #800080;">0</span> ; i < <span style="color: #800080;">4</span> ; i++<span style="color: #000000;">)
</span><span style="color: #008080;"> 93</span> <span style="color: #000000;"> {
</span><span style="color: #008080;"> 94</span> <span style="color: #000000;"> node next;
</span><span style="color: #008080;"> 95</span> next.x = pre.x +<span style="color: #000000;"> dx4[i];
</span><span style="color: #008080;"> 96</span> next.y = pre.y +<span style="color: #000000;"> dy4[i];
</span><span style="color: #008080;"> 97</span> next.d = pre.d + <span style="color: #800080;">1</span><span style="color: #000000;">;
</span><span style="color: #008080;"> 98</span> <span style="color: #0000ff;">if</span><span style="color: #000000;"> (next.ok())
</span><span style="color: #008080;"> 99</span> <span style="color: #000000;"> {
</span><span style="color: #008080;">100</span> v[next.x][next.y] = <span style="color: #0000ff;">true</span><span style="color: #000000;">;
</span><span style="color: #008080;">101</span> <span style="color: #000000;"> q.push(next);
</span><span style="color: #008080;">102</span> <span style="color: #000000;"> }
</span><span style="color: #008080;">103</span> <span style="color: #000000;"> }
</span><span style="color: #008080;">104</span> <span style="color: #000000;"> }
</span><span style="color: #008080;">105</span> <span style="color: #0000ff;">return</span> <span style="color: #0000ff;">false</span><span style="color: #000000;">;
</span><span style="color: #008080;">106</span>
<span style="color: #008080;">107</span> <span style="color: #000000;">}
</span><span style="color: #008080;">108</span> <span style="color: #0000ff;">int</span><span style="color: #000000;"> main()
</span><span style="color: #008080;">109</span> <span style="color: #000000;">{
</span><span style="color: #008080;">110</span> <span style="color: #000000;"> #ifndef ONLINE_JUDGE
</span><span style="color: #008080;">111</span> freopen(<span style="color: #800000;">"</span><span style="color: #800000;">in.txt</span><span style="color: #800000;">"</span>,<span style="color: #800000;">"</span><span style="color: #800000;">r</span><span style="color: #800000;">"</span><span style="color: #000000;">,stdin);
</span><span style="color: #008080;">112</span> <span style="color: #0000ff;">#endif</span>
<span style="color: #008080;">113</span>
<span style="color: #008080;">114</span> <span style="color: #0000ff;">while</span> (scanf(<span style="color: #800000;">"</span><span style="color: #800000;">%d %d</span><span style="color: #800000;">"</span>,&w;,&h;)!=EOF&&w;&&<span style="color: #000000;">h)
</span><span style="color: #008080;">115</span> <span style="color: #000000;"> {
</span><span style="color: #008080;">116</span> ms(v,<span style="color: #0000ff;">false</span><span style="color: #000000;">);
</span><span style="color: #008080;">117</span> cnt = <span style="color: #800080;">0</span><span style="color: #000000;"> ;
</span><span style="color: #008080;">118</span> <span style="color: #0000ff;">for</span> ( <span style="color: #0000ff;">int</span> i = <span style="color: #800080;">0</span> ; i < w ; i++) scanf(<span style="color: #800000;">"</span><span style="color: #800000;">%s</span><span style="color: #800000;">"</span><span style="color: #000000;">,maze[i]);
</span><span style="color: #008080;">119</span>
<span style="color: #008080;">120</span> <span style="color: #0000ff;">for</span> ( <span style="color: #0000ff;">int</span> i = <span style="color: #800080;">0</span> ; i < w ; i++<span style="color: #000000;">)
</span><span style="color: #008080;">121</span> <span style="color: #0000ff;">for</span> ( <span style="color: #0000ff;">int</span> j = <span style="color: #800080;">0</span> ; j < h ; j++<span style="color: #000000;">)
</span><span style="color: #008080;">122</span> <span style="color: #000000;"> {
</span><span style="color: #008080;">123</span> <span style="color: #0000ff;">if</span> (maze[i][j]==<span style="color: #800000;">'</span><span style="color: #800000;">D</span><span style="color: #800000;">'</span><span style="color: #000000;">)
</span><span style="color: #008080;">124</span> <span style="color: #000000;"> {
</span><span style="color: #008080;">125</span> cnt++<span style="color: #000000;">;
</span><span style="color: #008080;">126</span> <span style="color: #0000ff;">if</span> (cnt==<span style="color: #800080;">1</span><span style="color: #000000;">)
</span><span style="color: #008080;">127</span> <span style="color: #000000;"> {
</span><span style="color: #008080;">128</span> fx[cnt] =<span style="color: #000000;"> i;
</span><span style="color: #008080;">129</span> fy[cnt] =<span style="color: #000000;"> j;
</span><span style="color: #008080;">130</span> s.x =<span style="color: #000000;"> i;
</span><span style="color: #008080;">131</span> s.y =<span style="color: #000000;"> j;
</span><span style="color: #008080;">132</span> s.d = <span style="color: #800080;">0</span><span style="color: #000000;"> ;
</span><span style="color: #008080;">133</span> v[i][j] = <span style="color: #0000ff;">true</span><span style="color: #000000;">;
</span><span style="color: #008080;">134</span> <span style="color: #000000;"> }
</span><span style="color: #008080;">135</span> <span style="color: #0000ff;">else</span>
<span style="color: #008080;">136</span> <span style="color: #000000;"> {
</span><span style="color: #008080;">137</span> fx[cnt] = i - fx[<span style="color: #800080;">1</span>]; <span style="color: #008000;">//</span><span style="color: #008000;">相对位移．</span>
<span style="color: #008080;">138</span> fy[cnt] = j - fy[<span style="color: #800080;">1</span><span style="color: #000000;">];
</span><span style="color: #008080;">139</span> <span style="color: #000000;"> }
</span><span style="color: #008080;">140</span> <span style="color: #000000;"> }
</span><span style="color: #008080;">141</span> <span style="color: #000000;"> }
</span><span style="color: #008080;">142</span>
<span style="color: #008080;">143</span> <span style="color: #0000ff;">if</span> (!<span style="color: #000000;">bfs())
</span><span style="color: #008080;">144</span> <span style="color: #000000;"> {
</span><span style="color: #008080;">145</span> puts(<span style="color: #800000;">"</span><span style="color: #800000;">Impossible</span><span style="color: #800000;">"</span><span style="color: #000000;">);
</span><span style="color: #008080;">146</span> <span style="color: #000000;"> }
</span><span style="color: #008080;">147</span> <span style="color: #000000;"> }
</span><span style="color: #008080;">148</span>
<span style="color: #008080;">149</span>
<span style="color: #008080;">150</span>
<span style="color: #008080;">151</span> <span style="color: #000000;"> #ifndef ONLINE_JUDGE
</span><span style="color: #008080;">152</span> <span style="color: #000000;"> fclose(stdin);
</span><span style="color: #008080;">153</span> <span style="color: #0000ff;">#endif</span>
<span style="color: #008080;">154</span> <span style="color: #0000ff;">return</span> <span style="color: #800080;">0</span><span style="color: #000000;">;
</span><span style="color: #008080;">155</span> }
View Code