2次元座標処理Tips

2次元平面上で何かをするような問題はよくある。

コンピュータ上で、実装する場合は、だいたい2次元配列を用意して処理をする。x[i][j]を座標(i, j)とみなして2次元平面を表現するわけだ。

例えば、”8個の接している点の中で自身と同じ値を持っているものの個数を数える”とか”上下左右の接している4点のみ移動できる時○○せよ。”なんて問題はよく見かける。

私も数問解いた記憶がある。。。

しかし、どうも上手く実装できない。

何故かコードが長くなってしまう。

関数化できない。。

こんなヘタレな悩みが昨日解決された。やっぱり人のソースコードを見るのは大事ですね。。

例によって、PKUの問題で説明します。

今回の問題は、Red and Black。まあよくある問題です。

で、これが私が書いたヘタレコード。。笑

view plainprint?

1. class Plot {  
2. public:  
3. int x;  
4. int y;  
5. Plot(int x, int y) {  
6. this->x = x;  
7. this->y = y;  
8. }  
9.   
10. };  
11.   
12. int main() {  
13. int w, h;  
14. for (;;) {  
15. cin >> w >> h;  
16. if (!w && !h)  
17. break;  
18.   
19. VS tiles;  
20. REP(i, h) {  
21. string tileLine;  
22. char c;  
23. REP(j, w) {  
24.  cin >> c;  
25.  tileLine += c;  
26. }  
27. tiles.PB(tileLine);  
28. }  
29.   
30. queue<Plot> prc;  
31. REP(i, h) {  
32. REP(j, w) {  
33.  if (tiles[i][j] == '@') {  
34.   prc.push(Plot(i, j));  
35.   break;  
36.  }  
37. }  
38. }  
39.   
40. int ret = 0;  
41. bool done[h][w];  
42. memset(done, 0, sizeof(done));  
43.   
44. while (prc.size()) {  
45. int x = prc.front().x;  
46. int y = prc.front().y;  
47. prc.pop();  
48. ++ret;  
49.   
50. if (x > 0) {  
51.  if (tiles[x - 1][y] == '.' && !done[x - 1][y]) {  
52.   prc.push(Plot(x - 1, y));  
53.   done[x - 1][y] = true;  
54.  }  
55. }  
56. if (x < h - 1) {  
57.  if (tiles[x + 1][y] == '.' && !done[x + 1][y]) {  
58.   prc.push(Plot(x + 1, y));  
59.   done[x + 1][y] = true;  
60.  }  
61. }  
62. if (y > 0) {  
63.  if (tiles[x][y - 1] == '.' && !done[x][y - 1]) {  
64.   prc.push(Plot(x, y - 1));  
65.   done[x][y - 1] = true;  
66.  }  
67. }  
68. if (y < w - 1) {  
69.  if (tiles[x][y + 1] == '.' && !done[x][y + 1]) {  
70.   prc.push(Plot(x, y + 1));  
71.   done[x][y + 1] = true;  
72.  }  
73. }  
74. }  
75. cout << ret << endl;  
76. }  
77.   
78. return 0;  
79. }  

class Plot {
public:
int x;
int y;
Plot(int x, int y) {
this->x = x;
this->y = y;
}

};

int main() {
int w, h;
for (;;) {
cin >> w >> h;
if (!w && !h)
break;

VS tiles;
REP(i, h) {
string tileLine;
char c;
REP(j, w) {
 cin >> c;
 tileLine += c;
}
tiles.PB(tileLine);
}

queue<Plot> prc;
REP(i, h) {
REP(j, w) {
 if (tiles[i][j] == '@') {
  prc.push(Plot(i, j));
  break;
 }
}
}

int ret = 0;
bool done[h][w];
memset(done, 0, sizeof(done));

while (prc.size()) {
int x = prc.front().x;
int y = prc.front().y;
prc.pop();
++ret;

if (x > 0) {
 if (tiles[x - 1][y] == '.' && !done[x - 1][y]) {
  prc.push(Plot(x - 1, y));
  done[x - 1][y] = true;
 }
}
if (x < h - 1) {
 if (tiles[x + 1][y] == '.' && !done[x + 1][y]) {
  prc.push(Plot(x + 1, y));
  done[x + 1][y] = true;
 }
}
if (y > 0) {
 if (tiles[x][y - 1] == '.' && !done[x][y - 1]) {
  prc.push(Plot(x, y - 1));
  done[x][y - 1] = true;
 }
}
if (y < w - 1) {
 if (tiles[x][y + 1] == '.' && !done[x][y + 1]) {
  prc.push(Plot(x, y + 1));
  done[x][y + 1] = true;
 }
}
}
cout << ret << endl;
}

return 0;
}

なんとか、4つの方向に同様の処理をしている部分を関数化したかったが、関数化するにも、2次元配列使っているので面倒臭いことになるなと考えて挫折。。。

で、他の人のソース見てたら、シンプルな方法があったので、頂きました。。（ごちそうさま。）

こんな感じ。

view plainprint?

1. const int dx[] = { -1, 1, 0, 0 };  
2. const int dy[] = { 0, 0, -1, 1 };  
3.   
4. int main() {  
5. int w, h;  
6. for (;;) {  
7. cin >> w >> h;  
8. if (!w && !h)  
9. break;  
10.   
11. VS tiles;  
12. REP(i, h) {  
13. string tileLine;  
14. char c;  
15. REP(j, w) {  
16.  cin >> c;  
17.  tileLine += c;  
18. }  
19. tiles.PB(tileLine);  
20. }  
21.   
22. queue<Plot> prc;  
23. REP(i, h) {  
24. REP(j, w) {  
25.  if (tiles[i][j] == '@') {  
26.   prc.push(Plot(i, j));  
27.   break;  
28.  }  
29. }  
30. }  
31.   
32. int ret = 0;  
33. bool done[h][w];  
34. memset(done, 0, sizeof(done));  
35.   
36. while (prc.size()) {  
37. int x = prc.front().x;  
38. int y = prc.front().y;  
39. prc.pop();  
40. ++ret;  
41. REP(i, 4) {  
42.  int xx = x + dx[i];  
43.  int yy = y + dy[i];  
44.   
45.  if (xx < 0 || xx > h - 1 || yy < 0 || yy > w - 1)  
46.   continue;  
47.  if (tiles[xx][yy] == '.' && !done[xx][yy]) {  
48.   prc.push(Plot(xx, yy));  
49.   done[xx][yy] = true;  
50.  }  
51. }  
52. }  
53. cout << ret << endl;  
54. }  
55.   
56. return 0;  
57. }  

const int dx[] = { -1, 1, 0, 0 };
const int dy[] = { 0, 0, -1, 1 };

int main() {
int w, h;
for (;;) {
cin >> w >> h;
if (!w && !h)
break;

VS tiles;
REP(i, h) {
string tileLine;
char c;
REP(j, w) {
 cin >> c;
 tileLine += c;
}
tiles.PB(tileLine);
}

queue<Plot> prc;
REP(i, h) {
REP(j, w) {
 if (tiles[i][j] == '@') {
  prc.push(Plot(i, j));
  break;
 }
}
}

int ret = 0;
bool done[h][w];
memset(done, 0, sizeof(done));

while (prc.size()) {
int x = prc.front().x;
int y = prc.front().y;
prc.pop();
++ret;
REP(i, 4) {
 int xx = x + dx[i];
 int yy = y + dy[i];

 if (xx < 0 || xx > h - 1 || yy < 0 || yy > w - 1)
  continue;
 if (tiles[xx][yy] == '.' && !done[xx][yy]) {
  prc.push(Plot(xx, yy));
  done[xx][yy] = true;
 }
}
}
cout << ret << endl;
}

return 0;
}

いや、だいぶシンプル。

始めに、変化量を予め定数の配列で確保しておけばいいですね！！ここでポイントは、2次元方向の変化量を次元毎に個別に持たせて2重ループで回そうって考えないことです。変化パターンをまとめて書きだして、それぞれのx変化量、y変化量を配列dx, dyに格納しましょう。