python opencv6 グレイスケールへの変換
cv2.cvtColor(img,cv2.COLOR_RGB2GRAY)を用いる.
imgread()で第二引数に0を指定しても同じ効果な気がする.
# -*- coding: utf-8 -*- import cv2 def main(): img = cv2.imread("cocoa.jpg",0) cv2.imshow("cocoa",img) img = cv2.imread("cocoa.jpg") gray = cv2.cvtColor(img, cv2.COLOR_RGB2GRAY) # RGB画像をグレースケールに変換 cv2.imshow("gray scale",gray) cv2.waitKey(0) cv2.destroyAllWindows() if __name__ == '__main__': main()
cv2.COLOR_RGB2GRAYの代わりにcv2.COLOR_BGR2HSVとすると下のようになった.
# -*- coding: utf-8 -*- import cv2 def main(): img = cv2.imread("cocoa.jpg") gray = cv2.cvtColor(img, cv2.COLOR_BGR2HSV) cv2.imshow("gray scale",gray) cv2.waitKey(0) cv2.destroyAllWindows() if __name__ == '__main__': main()
python opencv5 画像の重ねあわせ
im = im1 + im2という感じで重ねあわせられる(すごすぎ!)
im1,im2は同じサイズでなければならない.
# -*- coding: utf-8 -*- import cv2 def main(): # 2枚の画像をグレースケールで取得 im1 = cv2.imread("test1.png",0) im2 = cv2.imread("test2.png",0) # 画像データを重ねあわせ im = im1 + im2 cv2.imshow("test",im) cv2.waitKey(0) cv2.destroyAllWindows() # ウィンドウ破棄 if __name__ == '__main__': main()
合成画像ではどちらかの画像がはっきり見えているから単にピクセルを重ねただけではないようである.
python opencv4 画像のりサイズ
画像のりサイズにはcv2.resize()を使う.
引数には読み込んだ画像と,リサイズしたい高さと幅のタプル
#!/usr/bin/env python # -*- coding: utf-8 -*- import numpy as np import cv2 # Load an color image in grayscale original_size_img = cv2.imread('cocoa.jpg',1)#0:グレースケール 1:通常 height = original_size_img.shape[0]#高さ width = original_size_img.shape[1]#幅 half_size_img = cv2.resize(original_size_img,(height/2,width/2)) cv2.imshow("original_size",original_size_img) cv2.imshow("half_size",half_size_img) cv2.waitKey(0) cv2.destroyAllWindows()
python opencv3 画像の範囲切り取り+保存
#!/usr/bin/env python # -*- coding: utf-8 -*- import numpy as np import cv2 # Load an color image in grayscale img = cv2.imread('cocoa.jpg',1)#0:グレースケール 1:通常 cv2.imshow('cocoa',img)#読み込んだ画像を表示 x = 200 y = 200 width = 100 height = 100 src = img dst = src[y:y+height,x:x+width]#(x,y)-(x+w,y+h)の正方形範囲を切り取る cv2.imwrite('dst.jpg',dst)#画像を保存
python opencv2 画素へのアクセス
RGBではなくBGRの順にリストになっているのが注意
#!/usr/bin/env python # -*- coding: utf-8 -*- import numpy as np import cv2 # Load an color image in grayscale img = cv2.imread('cocoa.jpg',1)#0:グレースケール 1:通常 cv2.imshow('cocoa',img)#読み込んだ画像を表示 px = img[100,100]#画素へのアクセス print px print "blue:",img[100,100,0] print "green:",img[100,100,1] print "red:",img[100,100,0] cv2.waitKey(0)#キーを押すと終了 cv2.destroyAllWindows()
Basic Operations on Images — OpenCV 3.0.0-dev documentation
opencv.blog.jp
python opencv1 画像を読み込んで表示
#!/usr/bin/env python # -*- coding: utf-8 -*- import numpy as np import cv2 # Load an color image in grayscale img = cv2.imread('cocoa.jpg',0)#0:グレースケール 1:通常 cv2.imshow('cocoa',img)#読み込んだ画像を表示 cv2.waitKey(0)#キーを押すと終了 cv2.destroyAllWindows()
ABC026_C
※bukaという変数とkouhaiという変数が混ざって大変汚いコード
部下と上司の木を表現してある社員が部下を持たなければ1,
部下を持っていればその部下の中からmax(部下の給料)+min(部下の給料)+1を返す.
メモ化再起風に解いた.
#include <bits/stdc++.h> using namespace std; static const int MAX_N = 20; struct Node{ vector<Node*> kouhai; int kyuuryou; }; Node worker[MAX_N]; int solve(Node *p) { /* 引数(Node*) : 社員 返り値(int) : 給料 worker[num].kyuuryou */ if((int)p->kouhai.size()==0){//部下がいなければ //給料を1にセットしてから給料1を返す p->kyuuryou = 1; return 1; }else{//部下がいれば //部下全員の給料を求めmax(部下の給料)+min(部下の給料)+1を返す vector<int> buka_kyuuryou; int max_kyuuryou = INT_MIN; int min_kyuuryou = INT_MAX; for(int i=0;i<(int)p->kouhai.size();i++){ int tmp = solve(p->kouhai[i]);//部下p->kouhai[i]の給料 buka_kyuuryou.push_back(tmp); max_kyuuryou = max(tmp,max_kyuuryou); min_kyuuryou = min(tmp,min_kyuuryou); } p->kyuuryou = max_kyuuryou+min_kyuuryou+1; return p->kyuuryou; } } int main() { int n,x; cin>>n; for(int i=1;i<n;i++){ cin>>x; worker[x-1].kouhai.push_back(&worker[i]);//社員iの先輩は社員x-1 == 社員x-1の後輩は社員i } solve(&worker[0]); int ans = worker[0].kyuuryou; cout<<ans<<endl; return 0; }
より簡単な方法
部下が上司より後になるのを利用して後ろから計算していく.
int P[MAX_N];//給料 int minP[MAX_N];//部下の給料の最小値 int maxP[MAX_N];//部下の給料の最大値 int sub[MAX_N];//部下の人数 for(int i=N-1;i>=0;i--){ if(sub[i].size()==0){//部下が0人ならば P[1]=1;//給料は1 continue; } //部下がいるならば部下の中で最大+最小+1 maxP[i] = 0; minP[i] = (int)1e9; for(int j=0;j<(sub[i].size();j++){ maxP[i] = max(maxP[i],P[j]); minP[i] = min(minP[i],P[j]); } P[i] = maxP[i] + minP[i]; }
ABC029_C
'a','b','c'から構成できるn文字の文字列を全て挙げる問題.
n=2ならaa,ab,ac,ba,bb,bc,ca,cb,cc
文字が増えていくので文字列と文字列の長さを引数にした関数を作ればよい.
#include <bits/stdc++.h> using namespace std; char alphabet[4] = {'a','b','c'}; int n; void solve(string s,int cnt){ if(cnt == 0){//作っている文字列の長さがnならば cout<<s<<endl; return; } //作っている文字列の長さがn以下ならば //'a','b','c'のどれかを挿れる for(int i=0;i<3;i++){ solve(s+alphabet[i],cnt-1); } } int main() { cin>>n; string s = ""; solve(s,n); return 0; }
ifでreturn文使うよりもelse文を使ったほうが個人的には綺麗だと感じた.
void solve(string s,int cnt){ if(cnt == 0){//作っている文字列の長さがnならば cout<<s<<endl; }else{ for(int i=0;i<3;i++){ solve(s+alphabet[i],cnt-1); } } }
C++ setの要素の検索
setにある要素が含まれているか否かを判定するにはS.find(value)を用いる.
要素が含まれていない場合はS.end()を返す.
よって
if(S.find(x)!=S.end())cout<<"要素あり"; else cout<<"要素なし";
のように判定すればよい.
#include <bits/stdc++.h> using namespace std; int main() { set<int> S; S.insert(1); S.insert(2); if(S.find(2) != S.end()){ cout<<"2あり"<<endl; }else{ cout<<"2なし"<<endl; } if(S.find(3) != S.end()){ cout<<"3あり"<<endl; }else{ cout<<"3なし"<<endl; } return 0; }
レポート表紙
過去のGISTが見れなくなったので再掲
\documentclass[a4j]{jarticle} \usepackage{color} \usepackage{listings,jlisting} \usepackage{ascmac} \usepackage{url} % \lstset{ language={python}, backgroundcolor={\color[gray]{.85}}, basicstyle={\small}, identifierstyle={\small}, commentstyle={\small\ttfamily \color[rgb]{0,0.5,0}}, keywordstyle={\small\bfseries \color[rgb]{1,0,0}}, ndkeywordstyle={\small}, stringstyle={\small\ttfamily \color[rgb]{0,0,1}}, frame={tb}, breaklines=true, columns=[l]{fullflexible}, %numbers=left, xrightmargin=0zw, xleftmargin=3zw, numberstyle={\scriptsize}, stepnumber=1, numbersep=1zw, morecomment=[l]{//} } \usepackage[dvipdfmx]{graphicx} \begin{document} \begin{titlepage} \title{title} \author{author} \maketitle%タイトルを出力 \vspace{8cm} %\center{name} \thispagestyle{empty} \end{titlepage} \appendix \begin{thebibliography}{n} \bibitem{key1}%文献情報 \end{thebibliography} \end{document}
Ctrl+x h ;全範囲選択 Esc-w ;指定範囲コピー
TeX関連コマンド
$platex test.tex $dvipdfmx test.dvi $evince test.pdf
Project Euler 83 Path sum: four ways
問題を見た時からdijkstra法だと分かっていたが集中してやりたかったので敢えて取っておいた問題
#include <bits/stdc++.h> using namespace std; static const int WHITE = 1; static const int GRAY = 2; static const int BLACK = 3; static const int INF = 1<<21; static const int MAX_N = 1000; static const int N = 80; int d[N][N]; int color[N][N]; int M[N][N]; int sx,sy,gx,gy; int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1}; void dijkstra() { int mincost; //初期化 for(int y=0;y<N;y++){ for(int x=0;x<N;x++){ color[y][x]=WHITE; d[y][x]=INF; } } color[sy][sx]=GRAY; d[sy][sx]=M[sy][sx]; while(true){ //集合Sに隣接している頂点のうち最もコストの小さい頂点を探す mincost=INF; int uy=-1,ux=-1; for(int y=0;y<N;y++){ for(int x=0;x<N;x++){ if(color[y][x]!=BLACK && d[y][x]<mincost){ mincost=d[y][x]; uy=y;ux=x; } } } if(uy==-1 || ux==-1)break;//集合Sの更新が無かったら終了 color[uy][ux]=BLACK;//その頂点を集合Sに挿れる //集合Sに隣接している頂点のd[v]を更新 for(int i=0;i<4;i++){ int vy=uy+dy[i],vx=ux+dx[i]; if(0<=vy && vy<N && 0<=vx && vx<N){ if(color[vy][vx]!=BLACK){ if(d[vy][vx]>d[uy][ux]+M[vy][vx]){ d[vy][vx]=d[uy][ux]+M[vy][vx]; color[vy][vx]=GRAY; } } } } } } vector<string> split(const string &s, char delim) { //文字列から文字をkeyにして分割する vector<string> elems; stringstream ss(s); string item; while(getline(ss,item,delim)){ if(!item.empty()){ elems.push_back(item); } } return elems; } int main() { //test.txt からint型二次元配列をinput std::ifstream ifs("test.txt"); std::string str; int i=0,j; while(getline(ifs,str)) { std::cout<< str << std::endl; vector<string> s = split(str,','); for(int j=0;j<80;j++){ M[i][j] = atoi(s[j].c_str()); } i++; } cout<<"--------------------------"<<endl; sx=0,sy=0; gx=N-1,gy=N-1; dijkstra(); cout<<d[gy][gx]<<endl; return 0; }
C++でファイルの読み込み
複数行の,で区切られた数値を二次元配列に格納する処理
std::ifstream ifs("test.txt"); std::string str; int i=0,j; while(getline(ifs,str)) { std::cout<< str << std::endl; vector<string> s = split(str,','); for(int j=0;j<80;j++){ M[i][j] = atoi(s[j].c_str()); } i++; }
ABC020_C
2分探索と単一始点最短経路問題の問題
dijkstra法は二次元配列と頂点の番号を対応させて考えればよい.
#include <bits/stdc++.h> using namespace std; /* 考え方 1.2文探索でtmp<=tを満たす最大のtmpを見つける 2.dijkstra法で'#'の移動コストがtmpであるとして'S'->'G'への移動コストの最小値を求める */ #define ll long long int static const int WHITE = 1; static const int GRAY = 2; static const int BLACK = 3; static const int MAX_H = 10; static const int MAX_W = 10; static const ll MAX_T = 1e9; static const ll INF = INT_MAX; char maze[MAX_H][MAX_W+1]; ll h,w,t; ll dt[MAX_H][MAX_W];//頂点の始点からの最小距離 ll color[MAX_H][MAX_W];// ll sx,sy,gx,gy; ll dx[4]={1,0,-1,0},dy[4]={0,1,0,-1}; void dijkstra(ll tmp) { //次のマスが黒色'#'だったときの移動コストをtmpとしたときのdijkstra法を用いる ll mincost; //初期化 for(ll y=0;y<h;y++){ for(ll x=0;x<w;x++){ color[y][x] = WHITE; dt[y][x] = INF; } } color[sy][sx] = GRAY; dt[sy][sx]=0; while(true){ mincost=INF; ll uy=-1; ll ux=-1; for(ll y=0;y<h;y++){ for(ll x=0;x<w;x++){ if(color[y][x]!=BLACK && dt[y][x]<mincost){ mincost = dt[y][x]; uy=y;ux=x; } } } if(ux==-1 || uy==-1){ break; } color[uy][ux]=BLACK; for(ll i=0;i<4;i++){ ll vy = uy+dy[i],vx=ux+dx[i]; if(0<=vy && vy<h && 0<=vx && vx<w){ if(color[vy][vx]!=BLACK){ ll cost=0; if(maze[vy][vx]=='#')cost+=tmp; else cost+=1; if(dt[vy][vx]>dt[uy][ux]+cost){ dt[vy][vx]=dt[uy][ux]+cost; color[vy][vx]=GRAY; } } } } } } bool judge(ll tmp) { //tmp<=tであるかを判定 //次のマスが黒色'#'だったときの移動コストをtmpとしたときのdijkstra法を用いる dt[sy][sx] = 0; dijkstra(tmp); if(dt[gy][gx]<=t)return true; else return false; } int binarySearch(ll left,ll right) { //二分探索 if(left+1==right)return left; ll mid = (left+right)/2; if(judge(mid)){ return binarySearch(mid,right); }else{ return binarySearch(left,mid); } } int main(){ /* ios_base::sync_with_stdio(0); cin.tie(0); #ifndef ONLINE_JUDGE freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif */ //input cin>>h>>w>>t; for(int y=0;y<h;y++){ scanf("%s",maze[y]);//cin>>maze[y]; } //スタート地点とゴール地点を記録 for(int y=0;y<h;y++){ for(int x=0;x<w;x++){ if(maze[y][x]=='S'){ sx=x;sy=y; } if(maze[y][x]=='G'){ gx=x;gy=y; } } } int ans = binarySearch(0,MAX_T); cout<<ans<<endl; return 0; }
単一始点最短経路 dijkstra法
#include <bits/stdc++.h> using namespace std; static const int MAX_N = 100; static const int WHITE = 0;//未踏 static const int GRAY = 1;//確定している点と隣接 static const int BLACK = 2;//確定 static const int INF = 1<<21; int M[MAX_N][MAX_N] = {0};//隣接行列 int d[MAX_N] = {0};//最短経路コスト int color[MAX_N] = {WHITE}; int n,u,k,c,v; void dijkstra(int s){ int mincost; //初期化: 全ての頂点uに対してcolor[u]をWHITE, d[u]をINF, d[s]=0, p[s]=-1; for(int u=0;u<n;u++){ color[u] = WHITE; d[u] = INF; } d[s]=0; color[0] = GRAY; while(true){ mincost = INF; int u = -1; for(int i=0;i<n;i++){ if(color[i]!=BLACK && d[i]<mincost){ mincost = d[i]; u = i; } } if(u==-1){ break; } color[u]=BLACK; for(int v=0;v<n;v++){ if(color[v]!=BLACK && M[u][v]!=INF){ if(d[v]>d[u]+M[u][v]){ d[v]=d[u]+M[u][v]; color[v]=GRAY; } } } } } int main() { cin>>n; for(int i=0;i<n;i++){//隣接グラフは重みINFの辺に初期化しておく for(int j=0;j<n;j++){ M[i][j] = INF; } } for(int i=0;i<n;i++){//隣接リストから隣接グラフへ書き換える cin>>u>>k; for(int j=0;j<k;j++){ cin>>c>>v; M[u][c] = M[c][u] = v; } } //始点は0 dijkstra(0); for(int i=0;i<n;i++){ cout<<i<<" "<<d[i]<<endl; } return 0; }