学步园

郁闷，，这么水的题目。。。

那天比赛真的是nc了。。。。看到搜索题就怕。。。

另外。。。

BFS竟然有点忘记了。。。罪过罪过。。。。。

Netbeans的调试还是很不习惯。。。太可怕了。。。

纯BFS搜索题目。。。。代码写的非常搓。。。。用了3个GOTO。。。。

How Many People Can Survive<br /> Time Limit : 2000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)<br /> Total Submission(s) : 4 Accepted Submission(s) : 2<br /> Font: Times New Roman | Verdana | Georgia<br /> Font Size: ← →<br /> Problem Description<br /> Two opposing armies are lost in a big forest. The forest is dangerous ,because it is filled with poisonous gas . People can only survive by staying at the place that is surrounded by trees.As the two armies are opposing, if one army are able to move to the other one , they wil fight with each other. Only the army that with the more people will survive, if the number is equal, no one will survive. Now you are asked to find out how many people will survive.<br /> Input<br /> There are several test cases.<br /> Each case begins with an integer n and m (3<=n,m<=300) stands for the size of forest.<br /> Then follows n lines , each line contains m characters .<br /> ‘.’ Stands for empty place<br /> ‘#’Stands for tree and can’t been walked through<br /> ‘o’Stands for the first army<br /> ‘v’stands for the second army<br /> Output<br /> The output contains one line for each data set : two integers, p and q, stands for the number of the first army that can survive and the number of the second army that can survive.<br /> Sample Input<br /> 3 3<br /> ..#<br /> ovo<br /> …<br /> 10 10<br /> ...vvvoo..<br /> ##########<br /> #....oo.o#<br /> #..v.v...#<br /> #........#<br /> #..####..#<br /> #..#o.#..#<br /> #..#.v#..#<br /> #..####..#<br /> ##########<br /> Sample Output<br /> 0 0<br /> 3 0<br /> Author<br /> dandelion<br /> Source<br /> HDU 8th Programming Contest Online

/*<br /> * File: main.cpp<br /> * Author: Administrator<br /> *<br /> * Created on 2010年4月28日, 上午5:03<br /> */</p> <p>#include<stdlib.h><br /> #include<stdio.h><br /> #include<string.h><br /> #include<algorithm><br /> #include<iostream><br /> #include<deque><br /> using namespace std;</p> <p>/*<br /> *<br /> */<br /> struct PT {<br /> int x;<br /> int y;<br /> };</p> <p>void Fill(int n, int m, char Graph[][305]) {<br /> int i, j;<br /> for (i = 0; i <= n + 1; i++)<br /> Graph[i][0] = Graph[i][m + 1] = '*';<br /> for (i = 0; i <= m + 1; i++)<br /> Graph[0][i] = Graph[n + 1][i] = '*';<br /> }</p> <p>void BFS(int n, int m, char Graph[][305], int &O, int &V) {<br /> int i, j;<br /> int numO, numV, sumO = 0, sumV = 0;<br /> int plusX[] = {0, 1, 0, -1};<br /> int plusY[] = {1, 0, -1, 0};<br /> bool IsSurvive;<br /> deque<PT> Queue;<br /> int top = 0;<br /> PT pt, get;<br /> bool IsReturn;</p> <p>RETURN:<br /> IsReturn = false;<br /> for (i = 1; i <= n; i++)<br /> for (j = 1; j <= m; j++)<br /> if (Graph[i][j] != '#' && Graph[i][j] != '-') {<br /> pt.x = i;<br /> pt.y = j;<br /> Queue.push_back(pt);<br /> IsReturn = true;<br /> goto BFSSTART;<br /> }<br /> BFSSTART:<br /> IsSurvive = true;<br /> numO = 0;<br /> numV = 0;<br /> while (!Queue.empty()) {<br /> get = Queue.front();<br /> Queue.pop_front();<br /> if (Graph[get.x][get.y] == 'v')<br /> numV++;<br /> if (Graph[get.x][get.y] == 'o')<br /> numO++;<br /> Graph[get.x][get.y] = '-';</p> <p> for (i = 0; i < 4; i++) {<br /> if (Graph[get.x + plusX[i]][get.y + plusY[i]] == '*')<br /> IsSurvive = false;<br /> if (Graph[get.x + plusX[i]][get.y + plusY[i]] == 'v') {<br /> pt.x = get.x + plusX[i];<br /> pt.y = get.y + plusY[i];<br /> Queue.push_back(pt);<br /> numV++;<br /> Graph[get.x + plusX[i]][get.y + plusY[i]] = '-';<br /> }<br /> if (Graph[get.x + plusX[i]][get.y + plusY[i]] == 'o') {<br /> pt.x = get.x + plusX[i];<br /> pt.y = get.y + plusY[i];<br /> Queue.push_back(pt);<br /> numO++;<br /> Graph[get.x + plusX[i]][get.y + plusY[i]] = '-';<br /> }<br /> if (Graph[get.x + plusX[i]][get.y + plusY[i]] == '.') {<br /> pt.x = get.x + plusX[i];<br /> pt.y = get.y + plusY[i];<br /> Queue.push_back(pt);<br /> Graph[get.x + plusX[i]][get.y + plusY[i]] = '-';<br /> }<br /> }<br /> }<br /> if (IsSurvive) {<br /> if (numV > numO)<br /> sumV += numV;<br /> else if (numV < numO)<br /> sumO += numO;<br /> }<br /> if (IsReturn)<br /> goto RETURN;<br /> ANS:<br /> O = sumO;<br /> V = sumV;<br /> }</p> <p>int main() {<br /> char Graph[305][305];<br /> int n, m;<br /> int i, j;<br /> int O, V;<br /> while (scanf("%d%d", &n, &m) != EOF) {<br /> for (i = 1; i <= n; i++)<br /> scanf("%s", &Graph[i][1]);<br /> Fill(n, m, Graph);<br /> /*<br /> for (i = 0; i <= n + 1; i++) {<br /> for (j = 0; j <= m + 1; j++)<br /> printf("%c", Graph[i][j]);<br /> printf("/n");<br /> }<br /> */<br /> BFS(n, m, Graph, O, V);<br /> printf("%d %d/n", O, V);<br /> }<br /> return (EXIT_SUCCESS);<br /> }