AOJ 0016 Treasure Hunt

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0016&lang=jp

概要

最初、x=0,y=0でy軸方向に向かって立っている。
現在向いている方向にdisメートル進んで、右にdir度だけ回転する。
数回行い、終了後の座標を出力する。

解法

最初、原点で90度の方向を向いている。
現在向いている方向をangleとすると、
x方向に、dis*cos(angle)
y方向に、dis*sin(angle)
だけ進めばよい。
sin、cosの引数はラジアンを渡すので、角度に(Π/180)を掛けてやる。
進んだ後、角度を更新する。

コード

#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
#define PI (acos(-1))

int main()
{
    char c;
    double dis, dir, x = 0, y = 0, angle = 90;
    while (1) {
        cin >> dis >> c >> dir;
        if (dis == 0 && dir == 0) break;
        x += dis * cos(angle * PI / 180);  // ラジアン = 度数 * (Π / 180)
        y += dis * sin(angle * PI / 180);
        angle -= dir;
    }
    printf("%d\n", (int)x);
    printf("%d\n", (int)y);
    return 0;
}

AOJ 0015 National Budget

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0015&lang=jp

概要

80桁までの整数が二つ与えられる。
その和を出力する。
80桁を超える場合は"overflow"を出力する。

解法

unsigned intだと(0 ～ 4294967295)
unsigned long longだと(0 ～ 18446744073709551615)
なので80桁の整数は扱えない。
文字列で読み込んで下から順に計算していく。

JavaだとBigIntegerで簡単にできます。

コード

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        string s1, s2, ans = "";
        cin >> s1 >> s2;
        int len1 = s1.length() - 1;
        int len2 = s2.length() - 1;
        int mlen = max(len1, len2);
        int pre = 0;
        for (int i = 0; i <= mlen; i++) {
            int sum = pre;
            sum += (len1 >= 0) ? s1[len1--] - '0' : 0;
            sum += (len2 >= 0) ? s2[len2--] - '0' : 0;
            pre = sum / 10;
            sum -= pre * 10;
            ans += '0' + sum;
        }
        if (pre > 0) ans += '0' + pre;
        reverse(ans.begin(), ans.end());
        if (ans.length() > 80) {
            puts("overflow");
        }
        else {
            cout << ans << endl;
        }
    }
    return 0;
}

AOJ 0067 The Number of Island

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0067

概要

12×12の地図が与えられる。

島の数を出力せよ。

解法

深さ優先探索で解く。

左上から見ていき、「１」を見つけたら、上下左右に繋がっている場所をすべて「０」にする。

最後に島の数を出力する。

コード

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

#define MAPSIZE 12
vector<string> mapdata(MAPSIZE);
int mapsize;
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };

void dfs(int x, int y)
{
    mapdata[y][x] = '0';
    for (int i = 0; i < 4; i++) {
        int px = x + dx[i];
        int py = y + dy[i];
        if (px < 0 || px >= MAPSIZE || py < 0 || py >= MAPSIZE) continue;
        if (mapdata[py][px] == '0') continue;
        dfs(px, py);
    }
}

int main()
{
    while (1) {
        int ans = 0;
        for (int i = 0; i < MAPSIZE; i++) {
            cin >> mapdata[i];
            if (cin.eof()) { return 0; }
        }
        for (int i = 0; i < MAPSIZE; i++) {
            for (int j = 0; j < MAPSIZE; j++) {
                if (mapdata[i][j] == '0') continue;
                dfs(j, i);
                ans++;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}